[백준]JAVA - 7576번: 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

풀이

최근에 풀었던 미로탐색(2178번), 숨바꼭질(1697번) 문제와 동일한 유형이다.

이 문제를 풀어보기 전에 먼저 풀어보는 걸 추천한다.

 

위 문제를 풀었으면 bfs 방법에 대해서는 확실히 이해했다고 가정하고 간단하게 설명하겠다.

이번 문제는 익은 토마토를 기준으로 상하좌우 한 칸씩 모든 토마토를 익혀야하는 문제이다. 즉, bfs를 중간에 끊지말고 끝까지 돌려야한다는 의미이다.

 

2차원 배열이기 때문에 Node 라는 이름의 클래스를 생성해서 노드 형태로 Queue를 만들어준다.

이후에 토마토 배열에서 익은 토마토(1)을 찾아서 x, y 값을 Queue에 넣어준다.

Queue에 들어간 x, y 값을 기준으로 상하좌우를 보면서 토마토가 들어있지 않은 칸(-1)을 제외한 안익은 토마토(0)을 찾아서 +1씩 해주면서 Queue에 넣고 빼고를 반복해주면 된다.

 

예외로는 토마토가 들어있지 않은 칸(-1)가 상하좌우를 가로막고 있어서 더 이상 나아갈 수 없을 경우이다.

이건 그냥 bfs를 모두 돌린 후에 2중 for문으로 토마토 배열을 돌면서 0인 값이 있으면 -1을 반환해주면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
		
        class Node {
            int x;
            int y;
			
            public Node (int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
		
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int[] cx = {-1, 0, 1, 0};
        int[] cy = {0, -1, 0, 1};
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
		
        int[][] map = new int[M][N];
        Queue<Node> q = new LinkedList<>();
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                map[j][i] = Integer.parseInt(st.nextToken());
				
                if (map[j][i] == 1) {
                    q.add(new Node(j, i));
                }
            }
        }

        while (!q.isEmpty()) {
            Node now = q.poll();
			
            for (int i=0; i<4; i++) {
                int row = now.x + cx[i];
                int col = now.y + cy[i];
				
                if (row >= 0 && row < M && col >= 0 && col < N && map[row][col] == 0) {
                    map[row][col] = map[now.x][now.y] + 1;
                    q.add(new Node(row, col));
                }
            }
        }
		
        int max = -1;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                max = Math.max(max, map[j][i]);
				
                // 모든 토마토를 익히지 못 한 경우
                if (map[j][i] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }
		
        System.out.println(max-1);
    }
}