[인프런/BFS/12.토마토]

<<풀이>>

 

이 문제는 BFS 문제인데 너무 오랜만에 하다 보니 어려웠다 ㅋㅋ 하지만 해오던 것들이 있어서 차근차근 접근했을 때 이해하는데 어려움은 없었다.

 

BFS 문제를 풀 때에는 Queue를 사용해서 해야 한다. 우선 두개 똑같은 배열 board와 dis를 만들어 준다. 하나는 1만을 넣어주는 것이고 다른 하나는 +1이 계속 되어 총 날짜를 표현한다. 이렇게 셋팅을 해주고 처음에 1이 들어간 좌표를 Queue에 넣어준다. 그다음 시작을 하면 while 구문에서 인접한 토마토까지 변화를 다 주게 되었을 때까지 작동하게 되는데 중간에 1로 변한 것이 있다면 Q에 다시 넣어주고 또 다른 하나는 원래 값에서 +1을 해주고 넣어준다. 그렇게 마지막까지 while 이 돌고 나서 최종 확인으로 여전히 0이 있다면 -1을 출력하고 아니면 +1을 해줬던 dis에서 최댓값을 for문으로 찾아 반환하게 되면 그 값이 정답이 된다. 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point {
    public int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
        }

class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, dis;
    static int n, m;
    static Queue<Point> Q = new LinkedList<>();
   public 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 && board[nx][ny]==0) {
                    board[nx][ny] = 1;
                    Q.offer(new Point(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
   }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        board=new int[n][m];
        dis=new int[n][m];

        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                board[i][j] = in.nextInt();
                if (board[i][j] == 1) Q.offer(new Point(i, j));
            }
        }
        T.BFS();
        boolean flag = true;
        int answer = Integer.MIN_VALUE;
        for(int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (board[i][j] == 0) flag = false;
            }
        }
        if(flag) {
            for(int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    answer = Math.max(answer, dis[i][j]);
                }
            }
            System.out.println(answer);
        }else {
            System.out.println(-1);
        }
        
    }
}

 

 

 

결국에는 정말 쉽다는 거죠 ~! 하지만 어렵다는 것은 익숙하지 않은 것이다 ! 꾸준히 다시 코테 달려보자 !!