[BFS] 백준 #7576 / 토마토문제

문제를 꼼꼼히 읽고, 조건을 먼저 파악한 뒤에 문제를 푸는 습관을 들여야겠다.

간단한 문제인데, 너무 오래걸렸다.

이 문제를 풀면서 얻은바가 있다면

C++의 pair<int,int> 는 JAVA에서 Point Class 

사용 방법은 다음과 같다.

---

1. java.awt.Point를 import

2. Queue<Point> A = new LinkedList<Point>(); 로 선언.

3. A.add(new Point(a,b))로 삽입 가능.

4. 여기서 주의! A.poll 해버리면 두 좌표 모두 빠져나가기 때문에 A.peek().x, A.peek().y로 값을 뽑아낸 뒤에 A.poll로 빼내준다.

---

java.awt.Point가 궁금해서 Java Flatform에서 찾아서 요약한 결과 다음과 같았다.

---

public class인 Point class는 Point2D를 상속받고, Serializable을 implements하는 클래스.
참고로 int형만 들어올 수 있으므로, 좌표 값을 받을 때만 사용할 것!

---

문제는 간단히 요약하면 다음과 같다.

1. N x M의 2차원 토마토 상자가 있다.
2. 익은 토마토가 있거나, 덜 익은 토마토가 있거나, 없거나 세 가지 경우가 존재한다.
3. 익은 토마토의 상, 하, 좌, 우의 덜 익은 토마토는 익은 토마토로 진화한다.
4. 토마토는 저절로 익지 않고, 영향을 받아야만 익는다.
5. 모든 토마토가 익기 까지 걸리는 최소 일 수는 며칠인가?
(단, 상자의 일부 칸에는 토마토가 없을 수도 있다)

[Input]
1. 상자의 크기 M, N 을 입력 받는다.
2~ 상자 속 토마토 정보가 2차원 배열로 주어진다.

[Output]
익을 때까지 최소 날짜를 출력해야 한다.
처음부터 모든 토마토가 익은 경우 0을 출력한다.
토마토가 모두 익지 못하는 상황이면 -1을 출력한다.

위의 밑줄 친 칸이 이 문제의 핵심. 이것 때문에 100퍼에서 틀렸다는 질문이 많이 올라온다(나도 이거 때문에 틀렸다)

[How to Solve?]
1. 2차원 배열에 토마토 정보를 담는다.
2. 두 개의 큐를 이용한다.
3. 첫 번째 큐에는 맨 처음 토마토 정보를 입력 받을 때, 익은 토마토의 위치를 담는다.
4. 두 번째 큐에는 첫 번째 큐의 모든 토마토로 부터 영향을 받아 익어진 토마토들의 위치를 담는다.
5. 각각의 예외 조건을 삽입하여 BFS로 문제를 풀어준다.

[Code]

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;
 
public class boj_7576_tomato {
    private static int N, M; // N행 M열
    private static int Map[][];
    private static boolean visited[][];
    private static char state;
    private static int total;
    private static int xx[] = { -1, 1, 0, 0 };
    private static int yy[] = { 0, 0, -1, 1 };
 
    private static Queue<Point> A = new LinkedList<Point>();
    private static Queue<Point> B = new LinkedList<Point>();
 
    public static void bfs(int x, int y) {
        visited[x][y] = true;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + xx[i];
            int ny = y + yy[i];
            if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1)
                continue;
            if (visited[nx][ny])
                continue;
            if (Map[nx][ny] == 0) {
                Map[nx][ny] = 1;
                visited[nx][ny] = true;
                if (state == 'A')
                    A.add(new Point(nx, ny));
                else if (state == 'B')
                    B.add(new Point(nx, ny));
            }
        }
 
    }
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
 
        M = sc.nextInt();
        N = sc.nextInt();
 
        Map = new int[N][M];
        visited = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Map[i][j] = sc.nextInt();
                if (Map[i][j] == 1)
                    A.add(new Point(i, j));
            }
        }
 
        while (!A.isEmpty() || !B.isEmpty()) {
            if(A.size()==N*M) {
                System.out.println(0);
                return;
            }
            if (B.isEmpty()) {
                while (!A.isEmpty()) { // A가 비워져 있지 않다면
                    state = 'B';
                    int x = A.peek().x;
                    int y = A.peek().y;
                    A.poll();
                    bfs(x, y);
                }
            }
            else if (A.isEmpty()) {
                while (!B.isEmpty()) { // B가 비워져 있지 않다면
                    state = 'A';
                    int x = B.peek().x;
                    int y = B.peek().y;
                    B.poll();
                    bfs(x, y);
                }
            }
            total++;
        }
        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(total-1);
    }
}