[C++] 백준 7576번:토마토

문제 링크

7576번: 토마토

 

 

문제 설명

토마토 농장의 현재 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야 한다. 만약 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태면 -1을 출력해야 한다.

토마토가 익기 위해서는 익은 토마토와 인접해야만 한다.(다른 경우는 없다.) 여기서 인접해야 한다는 말의 의미는 상, 하, 좌, 우로 인접해야 한다는 것이다.(대각선은 안된다.)

 

 

문제 풀이

bfs를 사용하여 풀이할 수 있는 문제다. 원래는 bfs함수 내에서 큐를 선언하고 사용하지만 이번 문제에서는 전역으로 큐를 선언하였다. 이렇게 해야 하는 이유는 처음 토마토 농장의 상태가 들어왔을 때 익은 토마토가 여러 개일 수 있고 이를 관리하기 위해서다. (bfs함수 내에서 익지 않은 토마토의 상태를 익은 토마토의 상태로 바꿔주기 때문에 다시 돌려놓을 수 없다.) 

dist는 해당 위치에 도달하기까지 필요한 가장 최소의 일 수를 저장하는 배열이다. 따라서 처음에 입력 받은 토마토의 상태가 익은 토마토라면 해당 위치의 dist값은 0이 되어야 한다.(다른 토마토를 통해 익지 않아도 되기 때문)

이외에 몇가지 예외처리(모두 익었는지 체크)를 포함하여 평범한 bfs문제처럼 해결하면 된다.

 

 

코드

 

 

메모

bfs를 사용하는 문제에서 큐를 전역으로 선언하여 사용하는 것은 처음이었던 것 같다. 

+ dist를 초기화 하는 과정에서 10,000으로해서 39%에서 틀렸었는데 이는 10,000,000으로 수정해서 해결하였다.(1000x1000크기의 2차원 배열이기 때문에 1,000,000보다 큰 숫자로 초기화 해주어야 한다.)