백준 27211번: 도넛 행성 (c++ 코드)

 

문제 풀이

 Java로 풀려다가 시간 초과가 떠서 c++ 코드로 바꿔 해결했다.

(테스트가 끝나고 서치해보니 Java에서 Scanner 대신 BufferedReader로 입력을 받아 시간을 줄이는 방법이 있는 것 같았다.)

 

복잡한 그림이 같이 있어서 당황했는데 문제는 생각보다 간단하다. 입력받은 맵에서 0으로 표시된 구역의 개수를 리턴하면 된다. 단, 조건은 처음과 끝이 연결되어 있는 도넛 행성이라는 점이다. 첫번째 행은 마지막 행과, 첫번째 열은 마지막 열과 연결되어 있으므로 이 부분을 조심해야 한다.

 

0으로 표시된 구역의 개수를 구하는 유형의 문제는 무조건 dfs를 이용해 해결한다.

 

 

 

arr 배열에는 0과 1의 정보를 저장한다. visited 배열에는 해당 좌표의 방문 여부를 저장한다.

int arr[MAX][MAX];
bool visited[MAX][MAX];

 

findArea()라는 함수를 만들어 (i, j) 좌표를 방문했을 때 수행할 일들을 코드로 작성한다.

방문 여부를 true로 바꾼 다음, 상하좌우의 좌표에 대해 0이고, 이전에 방문한 적이 없다면 findArea() 함수를 다시 호출한다.

void findArea(int i, int j, int n, int m) {
	visited[i][j] = true;
	
	for (int d = 0; d < 4; d++) {
		int newX = i + dir[d][0];
		int newY = j + dir[d][1];
		
		if (newX < 0) newX = n-1;
		if (newX >= n) newX = 0;
		if (newY < 0) newY = m-1;
		if (newY >= m) newY = 0;
		
		if (arr[newX][newY] == 0 && !visited[newX][newY]) 
			findArea(newX, newY, n, m);
	}
}

 

단, 이 문제에서 0번째 행과 열은 n-1 행, m-1 열과 연결되어 있으므로 이 부분을 if 문으로 구현한다.

 

 

이제 마지막으로 main 함수에서 findArea 함수를 사용하면 된다.

모든 좌표에 대해 0이고, 방문한 적이 없다면 findArea() 함수를 호출하고, 구역의 개수를 1 증가시킨다.

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0 && !visited[i][j]) {
				findArea(i, j, n, m);
				answer++;
			}
		}
	}

 

 

답안 코드

#include <iostream>
#define MAX 1001

using namespace std;

int arr[MAX][MAX];
bool visited[MAX][MAX];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

void findArea(int i, int j, int n, int m) {
	visited[i][j] = true;
	
	for (int d = 0; d < 4; d++) {
		int newX = i + dir[d][0];
		int newY = j + dir[d][1];
		
		if (newX < 0) newX = n-1;
		if (newX >= n) newX = 0;
		if (newY < 0) newY = m-1;
		if (newY >= m) newY = 0;
		
		if (arr[newX][newY] == 0 && !visited[newX][newY]) 
			findArea(newX, newY, n, m);
	}
}

int main() {
	init();
	
	int n, m, answer = 0;
	
	cin >> n;
	cin >> m;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			visited[i][j] = false;
		}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0 && !visited[i][j]) {
				findArea(i, j, n, m);
				answer++;
			}
		}
	}
	
	cout << answer;
	
	
	return 0;
}