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

문제 링크

7569번: 토마토

 

 

문제 설명

바로 이전에 풀었던 문제와 연결되는 문제다. 단지 2차원에서 3차원으로 차원이 늘어난 것이 차이점이다. 간단하게 정리를 다시 해보면 토마토 농장의 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야한다.

만약 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태라면 -1을 출력해야 한다.

토마토가 익기 위해서는 익은 토마토와 인접해야만 하고 여기서 인접하다는 것은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이다.

 

 

풀이

이 문제 역시 bfs를 이용하여 풀 수 있다. bfs를 시작할 수 있는 위치가 여러개인 경우 전역으로 큐를 선언하는 방법을 사용하여 풀이할 수 있으며 여기서도 그렇게 문제를 해결했다. 

인접한 위치를 조금 더 편하게 조사하기 위해서 배열 3개를 선언해준다.

int dx[6] = {0,0,0,0,-1,1}

int dy[6] = {0,0,-1,1,0,0}

int dz[6] = {-1,1,0,0,0,0}

 

그러면 현재 좌표에서 for문으로 여섯 방향을 모두 확인할 수 있다.

 

dist는 해당 좌표까지 도달하는데 걸리는 날짜를 저장한다. 입력 받을 때 토마토가 익은 상태라면 0을, 아니라면 1,000,000,000으로 초기화 해줘야한다. bfs로 탐색하면서 dist값을 min으로 바꿔줄 것이기 때문이다. 더 자세한 내용은 아래 코드에 주석으로 달아두었으니 확인해보도록 하자.

 

 

코드