BOJ 7576, 토마토

백준 온라인 저지에서 본 지는 오래되었지만, 최근에 푼 BFS문제입니다.

N by M이 먼저 주어지며(입력은 M,N순서로 들어왔습니다) 익은 토마토가 있는 곳의 값은 1, 빈 곳의 값은 -1, 익지 않은 토마토가 있는 곳의 값은 0으로 입력이 주어집니다.

이 때, 주어진 예제를 보면 맨 처음 익은 토마토의 개수가 1개인 경우만 볼 수 있습니다. 하지만, 처음 입력으로 들어오는 익은 토마토의 개수가 1개가 아닐 수 있음에 주의해야 합니다.

이런 류의 문제는, 대부분 BFS로 해결할 수 있습니다. BFS는 전체 경우의 수를 탐색하는데도 쓰이지만, 각 시간별 상태를 탐색할 때 간단하게 사용할 수 있는 방법인 것 같습니다.

예제를 볼까요?

예제 입력 1 

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

문제에서 주어진 예제 1번입니다. 예제 1번에서 하루가 지나면 어떻게 될까요?

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1

하루가 지나면 위와 같은 상태가 됩니다. 

0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1

이틀이 지나면 위와 같은 상태가 됩니다.

0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
0 0 1 1 1 1

3일이 지나면 위와 같은 상태가 됩니다.

...

최종적으로 8일이 지나면, 구역 안에 있는 모든 토마토가 익게 됩니다.

이 문제는 BOJ 1697, 숨바꼭질 문제와 유사하게 모델링 할 수 있습니다. 단지 1차원에서 2차원으로 늘어난 것 뿐이죠!

그렇다면?

먼저, BFS는 queue를 이용해 할 수 있습니다. 입력을 받을 때, 익은 토마토가 있는 좌표 쌍을 struct로 묶든, C++의 경우엔 pair로 묶든,  JAVA면 Class로 묶든 index가 2개인 배열로 묶어서 queue에 삽입해줍니다.

그 다음, queue의 첫 번째 원소를 가져와 그 점부터 bfs를 시작해줍니다. BFS는 총 4방향입니다, 하지만 방향이 더 많아질 수 도 있으므로 다음과 같은 테크닉을 사용하는 것을 추천합니다.

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

위와 같이 방향 벡터(x,y)->(x-1,y)(x+1,y)(x,y-1)(x,y+1)를 지정해두면, for문 하나로 모든 방향을 손쉽게 탐색할 수 있습니다. 단, 위와 같이 탐색을 하는 경우엔 배열 참조 범위가 맵을 벗어나는 경우를 잊지 말아야 합니다.

queue의 첫 번째 원소에서 시작한 경우를 예제를 통해 따라가 보겠습니다.

단, 좌표의 형식은 (열, 행) 입니다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

위의 경우, 현재 queue의 상태는 [(5,3)]입니다.

그럼, queue의 첫 번째 원소인 [(5,3)]을 빼서 전 방향 탐색을 해보겠습니다.

[(5,3+1)] = 맵의 범위를 벗어남.

[(5,3-1)] = 값이 0이므로, map[5][3-1] = map[5][3]+1

[(5+1,3)] = 맵의 범위를 벗어남.

[(5-1,3)] = 값이 0이므로, map[5-1][3] = map[5][3] +1

이 됩니다. 그리고, 값이 삽입된 [(5,2), (4,3)]을 queue에 삽입합니다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 2
0 0 0 0 2 1

위의 경우, 현재 queue의 상태는 [(5,2), (4,3)]입니다.

그럼, queue의 첫 번째 원소인 [(5,2)]을 빼서 전 방향 탐색을 해보겠습니다.

[(5,2+1)] = 0이 아니므로 pass

[(5,2-1)] = 값이 0이므로, map[5][2-1] = map[5][2]+1

[(5+1,2)] = 맵의 범위를 벗어남.

[(5-1,2)] = 값이 0이므로, map[5-1][3] = map[5][3] +1

이 됩니다. 그리고, 값이 삽입된 [(5,1), (4,2)]을 queue에 삽입합니다.

... 위와 같이 queue가 빌때까지 위의 알고리즘을 반복해줍니다. 그럼 다음과 같은 map을 얻을 수 있습니다.

9 8 7 6 5 4
8 7 6 5 4 3
7 6 5 4 3 2
6 5 4 3 2 1

맵을 전부 탐색해 준 다음, 0이 발견되는 경우 토마토가 전부 익을 수 없는 경우로 condition을 걸어 주고, 맵에서 토마토가 익는데 가장 오래 걸리는 시간을 찾아줍니다. 이 경우에는, 0일째를 1부터 더하기 시작했으니 최종 답에서 1을 뺴줘야합니다.

따라서 위 예제의 답은 9-1 = 8이 되는 것입니다.

위의 알고리즘을 사용하면 토마토 문제를 해결하실 수 있습니다.