๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[์ธํ”„๋Ÿฐ/BFS/12.ํ† ๋งˆํ† ]

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2024. 5. 19.

<<ํ’€์ด>>

 

์ด ๋ฌธ์ œ๋Š” 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);
        }
        
    }
}

 

 

 

๊ฒฐ๊ตญ์—๋Š” ์ •๋ง ์‰ฝ๋‹ค๋Š” ๊ฑฐ์ฃ  ~! ํ•˜์ง€๋งŒ ์–ด๋ ต๋‹ค๋Š” ๊ฒƒ์€ ์ต์ˆ™ํ•˜์ง€ ์•Š์€ ๊ฒƒ์ด๋‹ค ! ๊พธ์ค€ํžˆ ๋‹ค์‹œ ์ฝ”ํ…Œ ๋‹ฌ๋ ค๋ณด์ž !!

๋Œ“๊ธ€