20.11.02 - [백준] 7576번 토마토

[guswns1659]

문제 풀이 핵심 아이디어

• 여러 시작점에서 모든 지점으로의 거리를 구하는 문제
• 시작점이 여러개 있기 때문에 큐에 모든 시작점을 넣는다. -> 이중for문으로 돌면 시간 초과가 발생한다.

---

• dist을 초기화할 때 모든 시작점을 큐에 넣어야하기 때문에 queue를 미리 생성한다. (기존엔 dfs 함수 내에서 생성함)
• 입력되는 행과 열이 반대로 입력되기 때문에 주의해서 받는다.
• dist를 초기화한다.
  • tomatoStatus == 1인 경우 해당 좌표를 큐에 넣는다.
  • tomatoStatus == 0인 경우 dist[x][y]에 -1를 넣는다. (그럼, 없는 경우나 익은 토마토일 경우 0으로 초기화된다.)
• while(!q.isEmpty())를 돌면서 체크하되
  • 배열 범위 내에 있는지 확인
  • 만약 dist[x2][y2] >= 0일 경우 continue (안 익은 토마토가 아닐경우)
  • 위 조건을 벗어나면 dist[x2][y2] = dist[location[0]][location[1]] + 1;한다
• dist를 탐색하면서
  • -1일 경우 (안 익은 토마토가 있는 경우) -1 출력
  • 그 외에는 기존 최댓값과 비교해서 최대값을 출력

어려운점 및 실수

• 마지막 dist를 탐색할 때 인덱스를 row가 아니라 N을 넣어서 인덱스를 벗어난 에러 발생
• dist를 사용하면 visited를 사용하지 않아도 된다!!

풀이

package backjun.bfs;

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

public class N7576 {

    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    static int[][] dist;
    static int M, N;
    static Queue<int[]> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] MN = br.readLine().split(" ");
        M = Integer.parseInt(MN[0]);
        N = Integer.parseInt(MN[1]);

        dist = new int[N][M];

        // map과 dist 초기화
        for (int row = 0; row < N; row++) {
            String[] oneRow = br.readLine().split(" ");
            for (int column = 0; column < M; column++) {
                int tomatoStatus = Integer.parseInt(oneRow[column]);
                if (tomatoStatus == 1) {
                    q.offer(new int[]{row, column});
                }
                if (tomatoStatus == 0) {
                    dist[row][column] = -1;
                }
            }
        }

        // dfs 과정, 모든 시작점으로부터 거리 구함
        while (!q.isEmpty()) {
            int[] location = q.poll();

            for (int dir = 0; dir < 4; dir++) {
                int x2 = location[0] + dx[dir];
                int y2 = location[1] + dy[dir];

                if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M) continue;
                // 익은 토마토거나 비어있는 경우
                if (dist[x2][y2] >= 0) continue;
                q.offer(new int[]{x2,y2});
                dist[x2][y2] = dist[location[0]][location[1]] + 1;
            }
        }

        /*
         * dist를 돌면서 -1이 있으면 안 익은 토마토가 있는 상황이라 -1 출력
         * 그 외에는 없는 토마토거나 익은 토마토가 있는 상황이라 최대값을 출력한다.
         */
        int max = 0;
        boolean flag = true;
        for (int row = 0; row < N; row++) {
            for (int column = 0; column < M; column++) {
                if (dist[row][column] == -1) {
                    flag = false;
                }
                max = Math.max(max, dist[row][column]);
            }
        }

        if (!flag) {
            System.out.println(-1);
        } else {
            System.out.println(max);
        }
    }
}