[Baekjoon] 7576 - 토마토

📝 문제

 

🔑 풀이 과정

· BFS(너비 우선 탐색) 문제

 

· 0일차(기본 상태)에 익은 토마토는 1, 1일차에 익은 토마토는 2, 2일차에 익은 토마토는 3... i-1일차에 익은 토마토는 i값을 가지게 했다.

 

· 지금까지 풀었던 BFS 문제들은 시작점이 정해져있는 탐색 문제였다(ex. 미로문제). 그런데 이번에는 1값을 가진 위치에서 동시에 탐색을 시작했어야 했는데 이걸 어떻게 풀이하는지가 어려웠다. 그러나 해결은 생각보다 간단했다. 시작점인 위치를 전부 queue에 미리 집어넣으면 되는 것.

 

· 입력받을 때 값이 1인 위치들을 큐에 다 집어 넣는다. → BFS 수행 → 배열(상자)을 전체 탐색하면서 0이 있으면(안익은 토마토) 바로 탐색을 종료하고 -1을 출력하게 하고, 만약 없다면 배열내의 최댓값을 구하고 그 최댓값에서 -1을 뺀 값을 출력한다.

 

· 이 문제는 방문배열이 필요가 없다. 0이면 안익은 토마토이므로 걔만 queue에 넣어주면 되는 것.

 

· 예제3을 그림으로 표현

 

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

    static Queue<int[]> queue = new LinkedList<>();

    static int N;
    static int M;

    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); //가로 칸의 수
        N = Integer.parseInt(st.nextToken()); //세로 칸의 수

        arr = new int[N][M];

        for(int i = 0 ; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                int value = Integer.parseInt(st.nextToken());
                arr[i][j] = value;

                if(value == 1) //익은 토마토를 큐에 삽입
                    queue.add(new int[] {i, j});
            }
        }
        //입력 종료

        //BFS수행
        BFS();

        //다 끝난 후 검사
        int max = 0;
        loop:
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 0){
                    max = 0;
                    break loop;
                }

                if(arr[i][j] > max)
                    max = arr[i][j];
            }
        }

        bw.write((max-1) + "\n");
        bw.flush();
        bw.close();

    }

    static void BFS(){
        while(!queue.isEmpty()){
            int[] now = queue.remove();
            int nowX = now[0];
            int nowY = now[1];

            for(int i = 0; i < 4; i++){
                int x = nowX + dx[i];
                int y = nowY + dy[i];

                if((x >= 0) && (x < N) && (y >= 0) && (y < M)){
                    if(arr[x][y] == 0){
                        queue.add(new int[] {x, y});
                        arr[x][y] = arr[nowX][nowY] + 1;
                    }
                }
            }
        }

    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색