ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

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

 

7576๋ฒˆ: ํ† ๋งˆํ† 

์ฒซ ์ค„์—๋Š” ์ƒ์ž์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋‘ ์ •์ˆ˜ M,N์ด ์ฃผ์–ด์ง„๋‹ค. M์€ ์ƒ์ž์˜ ๊ฐ€๋กœ ์นธ์˜ ์ˆ˜, N์€ ์ƒ์ž์˜ ์„ธ๋กœ ์นธ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹จ, 2 ≤ M,N ≤ 1,000 ์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ๋Š” ํ•˜๋‚˜์˜ ์ƒ์ž์— ์ €์žฅ๋œ ํ† ๋งˆํ† 

www.acmicpc.net

์ดํ•ด

ํ’€์ด์— ์•ž์„œ ๋ฌธ์ œ๋ฅผ ์ดํ•ดํ•ด๋ณด์ž

  • ํ† ๋งˆํ† ์˜ ์ต์€ ์ƒํƒœ๊ฐ€ 1์ดˆ๋งˆ๋‹ค 1์นธ์”ฉ ์ „์ด๋˜๋Š” ์ƒํ™ฉ์ด๊ณ 
  • ์ „์ฒด ํ† ๋งˆํ† ์— ์ „์ด๋˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์ตœ์†Œ ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•ด์•ผํ•œ๋‹ค
  • ๊ฒฐ๊ตญ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•ด์•ผํ•˜๊ณ , ๊ฐ ์ขŒํ‘œ์— ์ตœ์†Œ ์‹œ๊ฐ„์„ ๊ธฐ๋กํ•ด์•ผํ•˜๋ฏ€๋กœ BFS๋ฅผ ์ด์šฉํ•ด์•ผํ•œ๋‹ค
  • BFS๋ฅผ ์ง„ํ–‰ํ•˜๋ฉฐ cost๋ฅผ ๊ธฐ๋กํ•˜๊ณ  ํƒ์ƒ‰ ์ข…๋ฃŒ ํ›„์— cost ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค

ํ’€์ด

์—ฌ๊ธฐ์„œ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋Š” ์ต์€ ํ† ๋งˆํ†  ์—ฌ๋ถ€๋กœ ํ•œ๋‹ค = 1์ด๋ฉด visited=true

    1. ์ต์€ ํ† ๋งˆํ† ๋ฅผ ์ฐพ์•„ queue์— ์ถ”๊ฐ€
    2. BFS๋ฅผ ์ด์šฉํ•ด ํƒ์ƒ‰ํ•˜๋ฉฐ ๋‹ค์Œ ๊ณผ์ •์„ ๋”ฐ๋ฆ„
        1) ํ˜„์žฌ ์ขŒํ‘œ์™€ ์—ฐ๊ฒฐ๋œ ์ขŒํ‘œ๋ฅผ ์ด๋™๊ฐ€๋Šฅํ•œ์ง€ ๊ฒ€์‚ฌ (!isOutBound && map[y][x] == 0)
        2) ์ด๋™๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•˜๊ณ  cost๋ฅผ ๊ธฐ๋กํ•œ๋‹ค.
        3) ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ queue์— ์ถ”๊ฐ€ํ•œ๋‹ค.
    3. BFS ์ข…๋ฃŒ ์ดํ›„์— ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ์ต์ง€ ์•Š์€ ํ† ๋งˆํ† ๊ฐ€ ์žˆ๋‹ค๋ฉด -1์„ ์ถœ๋ ฅํ•œ๋‹ค
    4. ๋ชจ๋“  ํ† ๋งˆํ† ๊ฐ€ ์ต์€ ์ƒํƒœ๋ผ๋ฉด cost์— ๊ธฐ๋กํ•œ ๊ฐ’๋“ค ์ค‘ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

์ฝ”๋“œ

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

public class ํ† ๋งˆํ† _7576 {
    static class Point {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int M;
    static int N;
    static int[][] map;
    static int[][] cost;


    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");

        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);

        map = new int[N][M];
        cost = new int[N][M];

        for (int y = 0; y < N; y++) {
            String[] line = br.readLine().split(" ");
            for (int x = 0; x < line.length; x++) {
                map[y][x] = Integer.parseInt(line[x]);
            }
        }

        bfs();

        int result = calculateResult();

        bw.write(Integer.toString(result));

        bw.close();
        br.close();
    }

    static void bfs() {
        Queue<Point> queue = new LinkedList<>();

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 1) {
                    queue.add(new Point(x, y));
                }
            }
        }

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            int x = current.getX();
            int y = current.getY();

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

                boolean isOutBound = nextX < 0 || nextY < 0 || nextX >= M || nextY >= N;
                if (isOutBound) {
                    continue;
                }

                boolean isAvailable = map[nextY][nextX] == 0;
                if (isAvailable) {
                    map[nextY][nextX] = 1;
                    cost[nextY][nextX] = cost[y][x] + 1;
                    queue.add(new Point(nextX, nextY));
                }
            }
        }
    }

    static int calculateResult() {
        int result = -1;
        mapLoop:
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                if (map[y][x] == 0) {
                    result = -1;
                    break mapLoop;
                }

                result = Math.max(result, cost[y][x]);
            }
        }
        return result;
    }

}
๋ฐ˜์‘ํ˜•