[백준] 7576번 - 토마토 (Java)(○)

 

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

7576번: 토마토

 

<문제해석>

1. 토마토를 보관하는 창고(N * M)이 있다. 칸 마다 토마토를 보관한다.
2. 토마토는 익은 것과 덜 익은 것들이 섞여 있다.
3. 보관 후 하루가 지나면 잘 익은 토마토의 상/하/좌/우에 있는 토마토들도 익게 된다.
4. 토마토가 혼자서 익는 경우는 없고 반드시 영향을 받아서 익는다.
5. 창고의 토마토들이 모두 익게 되는 최소 일수를 구하라.
6. 상자의 일부 칸에 토마토가 없는 경우도 있다.

 

<문제풀이>

1. 상하좌우로 확산하면서 탐색하는 문제이므로 BFS 탐색 문제이다.
2. Queue에 저장할 Node class(int x, int y)를 선언한다.
3. 토마토가 익으면 맵 자체의 값을 0->1로 변경한다. (방문배열 X)
4. BFS탐색 전에 map을 for문을 돌려서 익은 토마토의 위치를 Queue에 넣고 동시에 BFS탐색을 시작하자.
5. 토마토가 익을 때마다 큐에 넣고 count+1 한다.
6. 더 이상 안익은 토마토가 없으면 탐색을 종료하고 결과를 출력한다.
7. 가지치기
   1. 맵 범위를 벗어나는 위치면 패스
   2. 이미 익은 토마토면 패스
8. 시작전에 모든 토마토가 1이면 0출력
9. BFS탐색 종료 후에 맵을 서치해서 0이 남아있으면 -1출력

 

<코드구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
 
public class Main {
    static int M, N;
    static int map[][];
    static int count = 0;
    static boolean checked[];
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    Queue<Node> Q = new LinkedList<>();
 
    class Node {
        int x, y, count;
        Node (int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
 
    void BFS() {
        while(!Q.isEmpty()) {
            Node now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                // 가지치기
                if (nx<0 || nx>=N || ny<0 || ny>=M) continue; // 맵 범위 벗어나면 패스
                if (map[nx][ny] == 1) continue; // 익은 토마토면 패스
                if (map[nx][ny] == -1) continue; // 빈칸이면 패스
                // 탐색성공
                map[nx][ny] = 1; // 토마토 익히기
                Q.add(new Node(nx, ny, now.count+1));
                count = now.count+1; // 재배일수 +1 증가
            }
        }
    }
     
    void Solve() {
        // 익은 토마토 찾아서 큐에 넣기
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 1) {
                    Q.add(new Node(i, j, 0));
                }
            }
        }
        // (예외처리) 모든 토마토가 익었으면 0 출력 후 종료
        if (Q.size() == N*M) {
            System.out.println(0);
            return;
        }
        // 토마토 익히기 시작
        BFS();
        // (예외처리) 못익은 토마토 찾으면 -1 출력 후 종료
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }
        // 결과 출력
        System.out.println(count);
    }
 
    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());//열
        N = Integer.parseInt(st.nextToken());//행
        map = new int[N][M];
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<피드백 #1>

• 토마토가 익으면 어차피 방문할 필요가 없기 때문에 방문배열을 사용하지 않고 map[][]의 값을 변경하는 것으로 정했음.
• 처음에 이동거리(익는 날수)를 변수 하나로 관리해서 잘못된 값이 나와서 class 내부변수로 보관하도록 수정했음.
• "처음부터 모든 토마토가 익은 상태(0)면 0을 출력"을 구현할 때 이를 "익은 토마토가 없으면 0을 출력"으로 잘못 정의해서 97%에서 계속 실패했음.
• 문제 이해 후 코드 구현까지 1시간 정도 걸렸으나 문제를 잘못 이해하고 예외처리 한 것 때문에 디버깅에 30분을 허비했음. 실제 시험이었으면 이것 때문에 멘탈이 나갔을 듯.