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

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

7576번: 토마토

 

<문제 분석>

1. 익은 토마토는 1, 안익은 토마토는 0, 빈칸은 -1로 주어진다.

2. 익은 토마토의 상하좌우로 영향을 줘서 안익은 토마토가 하루가 지나면 익게 된다.

3. bfs 탐색으로 상하좌우로 탐색할 때 0이면 1로 바꾸고 탐색을 계속한다.

  3-1. 상하좌우 검색 후에 누적거리+1 을 하자.

4. 출발점이 없으니 메인함수에서 for문을 돌려서 1이 나오면 bfs를 호출하자.

5. 0이 -1로 둘러싸여 있으면 안 익는다. 이때 -1을 출력해야 한다.

  5-1. bfs 종료 후 map[][]을 검색해서 0이 나오면 -1을 출력하자.

 

<추가 분석>

1. InputData에서 입력받는 동시에 토마토를 찾아서 큐에 넣자.

  1-1. 큐는 FIFO이므로 처음 찾은 토마토들부터 큐에서 꺼내서 탐색을 시작한다.

  1-2. 동시다발적으로 탐색이 가능해짐.

2. 첫시작이 1부터 하기 때문에 마지막 최종거리에서 -1을 해줘야함.

3. map[][]에 방문하면 값을 업데이트 하기 때문에 visited[][] 필요없음.

 

import java.util.*;

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

public class Main {
    static int N, M;
    static int A[][];    
    Queue<Point> Q;

    void InputData() {
        Scanner in = new Scanner(System.in);
        Q = new LinkedList<Point>();
        M = in.nextInt();
        N = in.nextInt();
        A = new int[N][M];
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                A[i][j] = in.nextInt();
                if (A[i][j] == 1) {
                    Q.offer(new Point(i, j));
                }
            }
        }
    }

    class Point {
        int x;
        int y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

    void BFS() {
        while (!Q.isEmpty()) {
            Point tmp = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                // 스킵하는 조건문
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (A[nx][ny] != 0) continue; //안익은 토마토가 아니면 스킵
                // 다음 탐색지 업데이트
                Q.offer(new Point(nx, ny));
                A[nx][ny] = A[tmp.x][tmp.y]+1;// 다음 탐색지를 누적거리+1로 업데이트 함 
            }
        }
    }
        
    void Solve() {
        BFS();
        //printMap();
        int max = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (A[i][j] == 0) { //안익은 토마토가 남아있는 경우 : -1
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, A[i][j]);
            }
        }
        if (max == 1) //처음부터 토마토만 있는 경우 : 0
            System.out.println(0);
        else
            System.out.println(max-1);
    }

    void printMap() {
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                System.out.print(A[i][j]+" ");
            }
            System.out.println();
        }
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>