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

풀이 요약

BFS 혹은 dijkstra, DP 유사 문제.

풀이 상세

BFS

1. 벽 부수기 등의 BFS 문제를 떠올리자. 삼중 방문처리를 통해 구할 수 있다.

2. 탐색을 하면서 나올 수 있는 경우는 다음과 같은 2가지이다.

3. 만약 다음 갈 곳이 벽인 경우라면, 벽을 더 부술 수 있는 지 확인하고, 이전에 동일한 카운트만큼 벽을 부수었는지 확인한 뒤 조건이 성립한다면 다음좌표, 현재 벽+1, 현재 거리+1 담은 배열을 Queue 에 넣어주자.

4. 만약 다음 갈 곳이 길이라면, 현재 동일한 카운트만큼 벽을 부수었는지만 확인하여 조건이 성립한다면 다음좌표, 현재 벽, 현재 거리+1 를 담은 배열을 Queue 에 넣어주자.

5. 가장 처음 나오는 도착좌표의 거리 이동 값이 답이다.

6. 만약 모든 탐색이 끝났는데도 도착좌표에 도달하지 못하면 -1 을 반환하자.

Dijstra

1. 사실 Dijstra 라는 아니고 벽의 값을 이차원 배열에 저장하며 진행하는 DP 가 좀 더 맞는 말 인거 같다. 유사한 부분이 있어 Dijstra 라고 일단 했다. 이중 배열이어서 인지 확실히 삼중 방문처리보다는 빠르다.

2. 탐색을 하면서 나올 수 있는 경우는 다음과 같은 2가지이다.

3. 만약 다음 갈 곳이 벽인 경우라면, 벽을 더 부술 수 있는 지 확인하고, 현재 block[][] 의 다음좌표 인덱스에 저장된 값이 현재 벽+1 값 보다 큰 경우 : block[][] 값을 현재 벽+1 로 업데이트 하고, 다음좌표, 현재 벽+1, 현재 거리+1 담은 배열을 Queue 에 넣어주자.

4. 만약 다음 갈 곳이 길이라면, 현재 block[][] 의 다음좌표 인덱스에 저장된 값이 현재 벽 값 보다 큰 경우 : block[][] 값을 현재 벽 로 업데이트 하고, 다음좌표, 현재 벽, 현재 거리+1 담은 배열을 Queue 에 넣어주자.

5. 가장 처음 나오는 도착좌표의 거리 이동 값이 답이다.

6. 만약 모든 탐색이 끝났는데도 도착좌표에 도달하지 못하면 -1 을 반환하자.

배운점

• 다음 문제와 같은 경우는 벽 제한만 지킬 수 있다면 가장 적은 이동거리를 찾는 문제이므로 우선순위 큐를 쓰는 것이 오히려 독이 된다. (거리를 우선순위로 하여 오름차순 정렬해도 같은 답은 나온다. 단 정렬하느라 시간을 잡아먹어 오히려 시간 낭비이다)

BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, K;
    private static int[][] map;
    private static boolean[][][] visited;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};

    private static void input() throws Exception {
        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        map = new int[N][M];

        String str;
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
    }

    private static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        visited = new boolean[N][M][K + 1];
        q.add(new int[]{0, 0, 0, 1});
        visited[0][0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == N - 1 && cur[1] == M - 1) {
                return cur[3];
            }
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;

                boolean isBlock = map[nr][nc] == 1;
                if (isBlock && cur[2] + 1 <= K && !visited[nr][nc][cur[2] + 1]) {
                    visited[nr][nc][cur[2] + 1] = true;
                    q.add(new int[]{nr, nc, cur[2] + 1, cur[3] + 1});
                } else if (!isBlock && !visited[nr][nc][cur[2]]) {
                    visited[nr][nc][cur[2]] = true;
                    q.add(new int[]{nr, nc, cur[2], cur[3] + 1});
                }
            }
        }
        return -1;
    }

    private static void output() {
        System.out.println(bfs());
    }

    public static void main(String[] args) throws Exception {
        input();
        output();
    }
}

Dijstra와 유사한 무언가, 혹은 DP

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main2 {
    private static int N, M, K;
    private static int[][] map, block;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};

    private static void input() throws Exception {
        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());
        map = new int[N][M];
        block = new int[N][M];
        String str;
        for (int i = 0; i < N; i++) {
            str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
                block[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    private static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 0, 1});

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == N - 1 && cur[1] == M - 1) return cur[3];
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
                boolean isBlock = map[nr][nc] == 1;
                if (isBlock && cur[2] + 1 <= K && block[nr][nc] > cur[2] + 1) {
                    block[nr][nc] = cur[2] + 1;
                    q.add(new int[]{nr, nc, cur[2] +1, cur[3] + 1});
                } else if (!isBlock && block[nr][nc] > cur[2]) {
                    block[nr][nc] = cur[2];
                    q.add(new int[]{nr, nc, cur[2], cur[3]+1});
                }
            }
        }
        return -1;
    }

    private static void output() {
        System.out.println(bfs());
    }

    public static void main(String[] args) throws Exception {
        input();
        output();
    }
}