[BOJ 7576] 토마토 C++/Kotlin

 

7576번: 토마토

 

 

문제풀이

 

익은 토마토를 찾아서 BFS를 수행한다.

보통은 visited 배열을 쓰지만 이번에는 map 배열로 방문 여부를 표시해주었다.

0이면 방문하지 않았다는 의미이고 그 외의 경우에는 이미 방문했다는 의미이다.

익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들의 값을 map[x][y] + 1로 수정해서 방문 표시를 한다.

 

BFS가 끝난 후에는 전체 배열을 검사해서 익지 않은 토마토가 있는지 확인한다.

있다면 -1을, 없다면 map 배열의 최댓값을 찾아서 -1 해주면 된다.

 

최댓값 - 1인 이유는 익은 토마토가 1로 되어있어서 최소 일수 + 1인 상태이기 때문이다.

그리고 처음에 모든 토마토가 익어있는 상태라면 최댓값이 1이기 때문에 따로 체크하지 않아도 0을 출력한다.

 

 

 

이 과정을 정리하자면 다음과 같다.

 

 

1. 익은 토마토를 찾는다
2. BFS를 통해 인접한 곳에 있는 익지 않은 토마토를 찾아서 map[nx][ny] = map[x][y] + 1 해준다
3. 모든 익은 토마토들에 대해서 BFS 수행을 완료하면 익지 않은 토마토가 있는지 확인한다
4. 익지 않은 토마토가 있다면 -1, 없으면 최댓값 - 1을 출력한다

 

코드

 

C++ 코드

 

 

 

Kotlin 코드