BOJ 7576번 토마토 문제 자바(java) 풀이
문제정리
- 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토가 익게된다.
- 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 를 의미한다.
- 대각선 토마토에는 영향을 줄 수 없다.
- 모든 토마토가 익는데 필요한 최소 일 수를 구해라
- 토마토가 없는 칸이 있을 수 있다.
문제 풀이
- 최소 시간을 구해야 하므로 모든 방향으로 퍼져가며 토마토를 익게 해나가며 구해야한다. 즉 bfs를 이용하여 탐색합니다.
- 익은 토마토가 여러개인 경우도 있기 때문에 익은 토마토를 모두 list에 담고 bfs 시작시 queue에 익은 토마토 위치를 모두 집어 넣습니다.
- 그리고 bfs를 시작합니다. 움직이는 위치가 범위를 넘지 않고 방문하지 않았고 0인 경우(익지 않은 경우)에만 방문합니다.
- 그리고 움직이기 전 위치(x,y) 숫자보다 1 증가시켜가며 위치에 시간도 같이 저장합니다.
- 중간 중간에 위치에 같이 저장된 시간이 max 값 보다 크다면 값을 갱신해 나갑니다.
만약에 0이 하나라도 있다면 -1을 출력합니다.
모든 토마토가 익어있다면 max값은 1이되게 됩니다.(탐색을 하지 못해 초기 값 1이 제일 큰 수가 되기 때문에) => 0 출력
- 모두 익었다면 (0이 없다면) max 값을 출력합니다.
시간 줄이기
- bfs에서 queue에 넣을떄 바로 방문처리 함으로써 방문하지 않은 곳은 다시 방문하지 않도록 한다.
- 익은 토마토들의 위치를 구할때 따로 이중 for문을 써서 하지 않고 입력 받을때 처리 합니다.
- 걸리는 시간을 bfs로 탐색할때 max 값을 갱신해나가며 미리 update합니다.
처음에는 토마토가 모두 익었는지 안익었는지를 매번 탐색해서 시간초과가 났었습니다.
백준 7576번 토마토 자바 코드