๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐ŸŽ› Others.../- ์‹ค์ „ ๋ฌธ์ œ ํ’€์ด : PS

[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 2206๋ฒˆ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด

by Wonit 2021. 8. 15.

๋ฌธ์ œ

ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 2206๋ฒˆ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค.
์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

 

2206๋ฒˆ: ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ

N×M์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ๋งต์ด ์žˆ๋‹ค. ๋งต์—์„œ 0์€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ด๊ณ , 1์€ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๋ฒฝ์ด ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹น์‹ ์€ (1, 1)์—์„œ (N, M)์˜ ์œ„์น˜๊นŒ์ง€ ์ด๋™ํ•˜๋ ค ํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ตœ๋‹จ ๊ฒฝ๋กœ

www.acmicpc.net

 

์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž.

 

๋ฌธ์ œ ์ ‘๊ทผ

 

์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ผ BFS๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋‹ค.

 

์ง€๊ธˆ๊นŒ์ง€ ํ•ด๊ฒฐํ–ˆ๋˜ BFS ์—์„œ๋Š” ์ œ์ผ ์ดํ•ด๊ฐ€ ํž˜๋“ค์—ˆ๋˜ ๋ฌธ์ œ๋‹ค.

 

์ฒ˜์Œ์€ ๋ธŒ๋ฃจํŠธํฌ์Šค๋กœ ๋ฒฝ์„ ๋šซ๊ณ  bfs ๋ฅผ ์ˆ˜ํ–‰ํ–ˆ๋Š”๋ฐ ๊ณ„์†ํ•ด์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚˜์™€์„œ ๊ฒฐ๊ตญ ๋ธ”๋กœ๊ทธ์˜ ํž˜์„ ๋นŒ๋ ธ๋˜ ๋ฌธ์ œ๋‹ค.

 

์ •๋‹ต ์ฝ”๋“œ

public class Main {

    private static int n;
    private static int m;
    private static int[][] visited;
    private 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));

        String[] nm = br.readLine().split(" ");

        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);

        visited = new int[n][m];
        arr = new int[n][m];

        for(int i = 0; i < n; i++) {

            String[] s = br.readLine().split("");

            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
                visited[i][j] = Integer.MAX_VALUE;
            }
        }

        bw.write(String.valueOf(bfs()));

        bw.flush();
        bw.close();
    }

    private static int bfs() {

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};

        Queue<Position> queue = new LinkedList<>();

        queue.add(new Position(0, 0, 1, 0));
        visited[0][0] = 0;

        while(!queue.isEmpty()) {
            Position front = queue.remove();

            if(front.x == m - 1 && front.y == n - 1) return front.depth;

            for(int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];
                if(!(0 <= xx && xx < m && 0 <= yy && yy < n)) continue;

                if(visited[yy][xx] > front.breakWall) { // ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š๋Š” ๋…ธ๋“œ๋งŒ

                    if(arr[yy][xx] == 0) {
                        queue.add(new Position(xx, yy, front.depth + 1, front.breakWall));
                        visited[yy][xx] = front.breakWall;
                    }else {
                        if(front.breakWall == 0) {
                            queue.add(new Position(xx, yy, front.depth + 1, front.breakWall + 1));
                            visited[yy][xx] = front.breakWall + 1;
                        }
                    }
                }
            }
        }

        return -1;
    }

    private static class Position {
        int x, y, depth, breakWall;

        Position(int x, int y, int depth, int breakWall) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.breakWall = breakWall;
        }
    }
}

์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๋Œ“๊ธ€