[14442] 벽 부수고 이동하기 2

문제 링크 : https://www.acmicpc.net/problem/14442

14442번: 벽 부수고 이동하기 2

 

문제 해결 방법

벽 부수고 이동하기에서 K가 추가됐다.

벽 부수고 이동하기에서 visit 배열의 세 번째 값이 0 이면 벽을 안 부순 경우, 1 이면 벽을 부순 경우로 사용했다.

 

벽 부수고 이동하기 2에서는 visit 배열을 다음과 같이

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

선언하여 세번째 값으로 부순 벽의 개수를 확인하도록 했다.

나머지는 동일하다.

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
    static class Position {
        int r;
        int c;
        int cnt;
        int wall;

        public Position(int r, int c, int cnt, int wall) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.wall = wall;
        }
    }

    static int N, M, K;
    static char[][] map;
    static int[] dr = {0, 0, -1, 1};
    static int[] dc = {-1, 1, 0, 0};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();

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

        bfs();
    }

    private static void bfs() {
        Queue<Position> q = new LinkedList<>();
        boolean[][][] visited = new boolean[N][M][K + 1];
        q.add(new Position(0, 0, 1, 0));

        while (!q.isEmpty()) {
            Position cur = q.poll();

            if (cur.r == N - 1 && cur.c == M - 1) {
                System.out.println(cur.cnt);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextR = cur.r + dr[i];
                int nextC = cur.c + dc[i];

                if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M || visited[nextR][nextC][cur.wall]) continue;

                int nextCnt = cur.cnt + 1;

                if (map[nextR][nextC] == '0') {
                    q.add(new Position(nextR, nextC, nextCnt, cur.wall));
                    visited[nextR][nextC][cur.wall] = true;

                } else if (map[nextR][nextC] == '1') {

                    if (cur.wall < K && !visited[nextR][nextC][cur.wall + 1]) {
                        q.add(new Position(nextR, nextC, nextCnt, cur.wall + 1));
                        visited[nextR][nextC][cur.wall + 1] = true;
                    }
                }
            }
        }

        System.out.println(-1);
    }
}