[백준] 16933번 - 벽 부수고 이동하기 3 [Java]

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

 

[백준] 16933번 - 벽 부수고 이동하기 3 [Java]

[백준] 16933번 - 벽 부수고 이동하기 3 [Java]

---

1.  아이디어

 

이전 벽 부수고 이동하기 2 문제에서 벽을 낮에만 부술 수 있는 조건이 추가된 문제로 낮과 밤은 BFS에서 구하고 있는 최단거리를 통해 알아낼 수 있다.

---

2. 문제풀이

 

최단거리를 저장한 dist 변수는 첫 칸부터 센다는 조건에서 1로 시작하며 현재 낮이다. 이를 통해 dist가 홀수면 낮, 짝수면 밤이 된다. 기존 로직에서 벽을 부수는 상황에서 낮인지 밤인지만 조건문으로 확인해서 낮이면 동일하게 벽을 부수고 밤일 경우 낮이 될 때까지 기다려야하므로 방금 뽑은 노드를 다시 Queue에 넣어주면 된다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static class Node {
        int r;
        int c;
        int cntBrokenWall;

        public Node(int r, int c, int cntBrokenWall) {
            this.r = r;
            this.c = c;
            this.cntBrokenWall = cntBrokenWall;
        }
    }

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int dist = bfs(N, M, K, map);
        System.out.println(dist);
    }

    private static int bfs(int N, int M, int K, char[][] map) {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0));

        boolean[][][] visited = new boolean[N][M][1 + K];
        visited[0][0][0] = true;

        int dist = 1;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.poll();
                if (node.r == N - 1 && node.c == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = node.r + dr[dir];
                    int nc = node.c + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == '0') {
                        if (visited[nr][nc][node.cntBrokenWall]) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall));
                        visited[nr][nc][node.cntBrokenWall] = true;
                    } else {
                        if (node.cntBrokenWall < K) {
                            // 낮
                            if (dist % 2 == 1) {
                                if (visited[nr][nc][node.cntBrokenWall + 1]) continue;

                                q.offer(new Node(nr, nc, node.cntBrokenWall + 1));
                                visited[nr][nc][node.cntBrokenWall + 1] = true;
                            }
                            // 밤
                            else {
                                q.offer(node);
                            }
                        }
                    }

                }
            }

            dist++;
        }

        return -1;
    }

}

import java.io.*;
import java.util.*;

public class Main {

    private static class Node {
        int r;
        int c;
        int cntBrokenWall;

        public Node(int r, int c, int cntBrokenWall) {
            this.r = r;
            this.c = c;
            this.cntBrokenWall = cntBrokenWall;
        }
    }

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int dist = bfs(N, M, K, map);
        System.out.println(dist);
    }

    private static int bfs(int N, int M, int K, char[][] map) {
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(0, 0, 0));

        int[][] visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        visited[0][0] = 0;

        int dist = 1;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.poll();
                if (node.r == N - 1 && node.c == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = node.r + dr[dir];
                    int nc = node.c + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                    if (map[nr][nc] == '0') {
                        if (visited[nr][nc] <= node.cntBrokenWall) continue;

                        q.offer(new Node(nr, nc, node.cntBrokenWall));
                        visited[nr][nc] = node.cntBrokenWall;
                    } else {
                        if (node.cntBrokenWall < K) {
                            // 낮
                            if (dist % 2 == 1) {
                                if (visited[nr][nc] <= node.cntBrokenWall + 1) continue;

                                q.offer(new Node(nr, nc, node.cntBrokenWall + 1));
                                visited[nr][nc] = node.cntBrokenWall + 1;
                            }
                            // 밤
                            else {
                                q.offer(node);
                            }
                        }
                    }

                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기

 

- 3차원 boolean 타입 방문 체크

- 2차원 int 타입 방문 체크