[BOJ 7576] 토마토 (C++)

Problem

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

Comment

해당 문제는 '하루가 지나면 익은 토마토 주위에 있는 토마토들이 익는다'고 하는 문장에서 BFS로 풀어야 한다는 힌트를 얻을 수 있습니다. 따라서 BFS를 이용하여 문제를 풀어보겠습니다.

 

문제의 핵심은 익은 토마토 주위(상, 하, 좌, 우)에 있는 익지 않은 토마토를 찾아 다음날이 지나면 익게 되는 것입니다. 우리는 모든 토마토가 익은 총 일수가 필요한 것이니 1을 그대로 사용해서 일(Day)로 생각하고 풀어도 될 것입니다. 즉, 배열에 적혀있는 수 N-1(단, N != 0)이 그 토마토가 익는데 걸리는 일(Day)이라고 생각해도 된다는 것입니다. 

 

처음 프로그램이 실행되고 나서 토마토의 입력을 받은 후, 토마토가 익었다면 큐에 추가해줍니다. 추가된 큐는 입력이 끝난 후 하나씩 BFS를 실행하게 됩니다. 모든 원소들의 BFS가 끝난 후, tomato 배열의 원소값들을 하나씩 보면서 (제일 큰 숫자 - 1)이 토마토가 모두 익는데 걸리는 일(Day)입니다. 

 

예제 1을 천천히 따라가면서 어떻게 동작하는지 알아보겠습니다.

1일차에는 하나 있는 익은 토마토 주위에 익은 토마토가 생기게 됩니다 (총 3개).

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

 

2일차에는 세 개의 익은 토마토 주위에 생기게 됩니다 (총 6개).

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

 

3일차에는 네 개의 익은 토마토 주위에 생기게 됩니다 (총 10개).

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

 

4일차에는 네 개의 익은 토마토 주위에 생기게 됩니다 (총 14개).

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

 

5일차에는 네 개의 익은 토마토 주위에 생기게 됩니다 (총 18개).

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

 

6일차에는 세 개의 익은 토마토 주위에 생기게 됩니다 (총 21개).

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

 

6일차에는 두 개의 익은 토마토 주위에 생기게 됩니다 (총 23개).

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

 

7일차에는 두 개의 익은 토마토 주위에 생기게 됩니다 (총 23개).

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

 

Code

 

Result