[ 백준 ] 7576번 - 토마토

< 문제 정보 >

[ 문제 ]

  M X N으로 이뤄진 상자에 토마토가 담겨 있다. 익은 토마토 옆에 안 익은 토마토를 놓을 경우, 다음날에 익은 토마토로 변하게 된다. 안 익은 토마토의 상하좌우에 익은 토마토가 있을 경우에만 변하게 된다. 이 때 상자의 모든 토마토가 익을 때까지의 최소 날짜를 출력하는 문제

[ 예시 ]

• 입력

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

※ 6 : 상자의 가로 칸의 수(M), 4 : 상자의 세로 칸의 수(N)
※ 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토가 들어있지 않은 칸

• 출력

8

※ 저장될 때부터 모든 토마토가 익어있는 상태라면 0 출력
※ 모든 토마토가 익지 못하는 상황일 경우 -1 출력

[ 규칙 ]

• 2 ≤ M,N ≤ 1,000
• 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

[ 백준 ]

• BFS
• 링크

< 풀이 >

•   최소 날짜 수 계산을 위해 BFS 시작 전, 저장될 때부터 익은 토마토(1)의 인덱스 행렬을 큐에 넣고 시작하였다.
•   익은 토마토부터 시작했기에, 최종 날짜에서 -1을 해줘야 정확한 날짜가 도출된다.
  
  [ 입력 행렬 ]

  	0	1	2	3	4	5
  0	0	0	0	0	0	0
  1	0	0	0	0	0	0
  2	0	0	0	0	0	0
  3	0	0	0	0	0	1

  
  [ 최종 결과 행렬 ]

  	0	1	2	3	4	5
  0	9	8	7	6	5	4
  1	8	7	6	5	4	3
  2	7	6	5	4	3	2
  3	6	5	4	3	2	1

  → 9 - 1 = 8 출력 ※ 앞서 이야기했듯, 3행 5열은 이미 익은 토마토이기에 날짜계산에 포함해선 안 된다. 따라서 본래 의도대로라면, 2행 5열과 3행 4열은 1이여야한다.

< 코드 >

public class BeakJoon7576 {
    int[] dx = { 1, 0, -1, 0 };
    int[] dy = { 0, 1, 0, -1 };
    static int N, M;
    static Queue<int[]> queue = new LinkedList<>();
    static boolean[][] visited;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[][] graph = new int[M][N];
        for (int i=0;i<M;i++) {
            String s = bf.readLine();
            graph[i] = Stream.of(s.split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        BeakJoon7576 beakJoon7576 = new BeakJoon7576();
        visited = new boolean[M][N];
        beakJoon7576.findStart(graph);  // 값이 1인 인덱스들을 사전에 큐에 삽입
        beakJoon7576.bfs(graph);
    }
    private void findStart(int[][] graph) {
        for (int i=0;i<M;i++) {
            for(int j=0;j<N;j++) {
                if (graph[i][j] == 1) {
                    queue.add(new int[]{i, j}); // 큐 삽입
                    visited[i][j] = true;   // 방문 처리
                }
            }
        }
    }
    private void bfs(int[][] graph) {
        ans = -1;
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];
            for (int i=0;i<dx.length;i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
                if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N || visited[nextX][nextY])
                    continue;
                if (graph[nextX][nextY] == 0) {
                    ans = 0;
                    visited[nextX][nextY] = true;
                    graph[nextX][nextY] = graph[nowX][nowY] + 1;
                    queue.add(new int[] { nextX, nextY });
                }
            }
        }
        findResult(graph);
        System.out.println(ans-1);
    }
    private void findResult(int[][] graph) {
        for (int i=0;i<M;i++) {
            for (int j=0;j<N;j++) {
                // 익지 않은 토마토가 있을 경우, 함수 종료
                if (graph[i][j] == 0) {
                    ans = -1;
                    break;
                }
                if (graph[i][j] > ans)
                    ans = graph[i][j];
            }
            // 익지 않은 토마토가 있을 경우, 함수 종료
            if (ans == -1)
                break;
        }
        if (ans == -1)
            ans = 0;
    }
}

---