[백준] 7576 토마토 자바 BFS 문제 풀이 및 정답

 

문제 요약)

- 익은 토마토가 4방향의 토마토를 익히는데 1일씩 걸림

- 토마토가 없는 구간은 빈 구간

- 모든 토마토를 익히는데 걸리는 최소 일 수 구하기

 

주의점)

- 보통 세로, 가로 순서로 주는데 해당 문제는 가로, 세로 순서로 주어짐

- 출발점이 한 곳이 아닌 여러 곳일수도 있다.

- 토마토가 없는 곳으로 둘러싸여 있으면 평생 안익는 토마토 존재 가능

 

풀이)

BFS로 접근했을 때 가장 직관적인 방법은 토마토 있고 없고 표기할 맵, 방문배열, 거리를 표기할 거리배열 등 총 3개를 사용하면 가장 직관적으로 풀 수 있습니다. 하지만 거리 배열을 잘 활용하면 방문배의 역할도 같이 할 수 있기 때문에 메모리 낭비를 줄여나갈 수 있습니다. 배열을 어떻게 쓰든 시작점을 q에 차곡차곡 넣어놓은 뒤 4방향 탐색을 해나가면서 풀어나갈 수 있습니다.

 

java

닫기 줄바꿈

import java.util.LinkedList;
import java.util.Queue;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Tomato7576_3_blog {
​​​​static int[] dx = {-1, 0, 1, 0};
​​​​static int[] dy = {0, 1, 0, -1};
​​​​static int m,n;
​​​​static int[][] map, days;
​​​​static int answer = 0, remainTomato = 0;
​​​​public static void main(String[] args) throws IOException {
​​​​​​​​BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​String[] s = br.readLine().split(" ");

​​​​​​​​m = Integer.parseInt(s[0]); // 가로
​​​​​​​​n = Integer.parseInt(s[1]); // 세로

​​​​​​​​map = new int[n][m];
​​​​​​​​days = new int[n][m];

​​​​​​​​Queue<int[]> q = new LinkedList<>();

​​​​​​​​// 입력 채워주기 및 익은 토마토면 q에 넣기
​​​​​​​​for (int i=0; i<n; i++) {
​​​​​​​​​​​​s = br.readLine().split(" ");
​​​​​​​​​​​​for (int j=0; j<s.length; j++) {
​​​​​​​​​​​​​​​​map[i][j] = Integer.parseInt(s[j]);
​​​​​​​​​​​​​​​​if (map[i][j] == 0) {
​​​​​​​​​​​​​​​​​​​​remainTomato++;
​​​​​​​​​​​​​​​​} else if (map[i][j] == 1) {
​​​​​​​​​​​​​​​​​​​​q.offer(new int[] {i, j});
​​​​​​​​​​​​​​​​​​​​days[i][j] = 0;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​BFS(q);

​​​​​​​​if (remainTomato > 0) answer = -1;
​​​​​​​​System.out.println(answer);

​​​​}

​​​​static void BFS(Queue<int[]> q) {
​​​​​​​​while (!q.isEmpty()) {
​​​​​​​​​​​​int[] current = q.poll();

​​​​​​​​​​​​for (int k=0; k<4; k++) {
​​​​​​​​​​​​​​​​// 4방향 탐색
​​​​​​​​​​​​​​​​int nx = current[0] + dx[k];
​​​​​​​​​​​​​​​​int ny = current[1] + dy[k];
​​​​​​​​​​​​​​​​// out of index 방지
​​​​​​​​​​​​​​​​if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​// 토마토가 이미 있거나, 아예 없거나, 방문을 이미 했던 거면 패스
​​​​​​​​​​​​​​​​if (map[nx][ny] != 0 || days[nx][ny] > 0) {
​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​// 방문안했고 안 익은 토마토인 경우니까 q에 넣고 날짜 표기해주기, 채웠다는 표시로 remainTomato 하나씩 빼주기
​​​​​​​​​​​​​​​​q.offer(new int[] {nx, ny});
​​​​​​​​​​​​​​​​days[nx][ny] = days[current[0]][current[1]] + 1;
​​​​​​​​​​​​​​​​answer = Math.max(answer, days[nx][ny]);
​​​​​​​​​​​​​​​​remainTomato--;
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}