[BOJ] 14442.벽 부수고 이동하기 2(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

벽 부수고 이동하기 1 문제의 확장판이다.

기존에는 벽을 최대 한 번만 부술 수 있었다면

이번에는 벽을 최대 K번 부술 수 있다.

벽 부수고 이동하기 1을 풀었다면 !

벽을 부술 수 있는 범위만 변경해주면 되는 간단한(?) 문제다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ14442 {           static int N, M, K, res = -1, map[][];     static boolean visited[][][];     static int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };       static class pos {         // x좌표, y좌표, 지금까지 거리, 벽을 부순 횟수         int x, y, d, k;           public pos(int x, int y, int d, int k) {             this.x = x;             this.y = y;             this.d = d;             this.k = k;         }     }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           N = Integer.parseInt(st.nextToken()); // 세로         M = Integer.parseInt(st.nextToken()); // 가로         K = Integer.parseInt(st.nextToken()); // 부술 수 있는 횟수         map = new int[N][M];         visited = new boolean[N][M][K+1];           for (int i = 0; i < N; i++) {             String input = br.readLine();             for (int j = 0; j < M; j++) {                 map[i][j] = input.charAt(j) - '0';             }         }           Queue<pos> q = new LinkedList<>();         visited[0][0][0] = true;         // 시작 칸과 끝나는 칸도 거리에 포함         q.add(new pos(0, 0, 1, 0));           while (!q.isEmpty()) {             pos now = q.poll();             // 목적지에 도착             if(now.x == N-1 && now.y == M-1) {                 res = now.d;                 break;             }             // 상하좌우로 탐색             for (int d = 0; d < 4; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                 // 범위를 벗어날 경우 pass                 if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;                                  // 이동할 수 있는 곳으로 이동할 경우                 if(map[xx][yy] == 0) {                      // 이미 왔던 길일 경우 pass                     if(visited[xx][yy][now.k]) continue;                     q.add(new pos(xx,yy,now.d+1,now.k));                     visited[xx][yy][now.k] = true;                 }                 // 벽을 부수고 이동해야할 경우                 else {                     // 더이상 벽을 부술 수 없거나,                      if(now.k >= K) continue;                     // 이미 왔던 길일 경우 pass                     if(visited[xx][yy][now.k+1]) continue;                     // 벽을 부술 수 있다면 부수고 이동                      q.add(new pos(xx,yy,now.d+1,now.k+1));                     visited[xx][yy][now.k+1] = true;                 }             }         }                  System.out.println(res);     } } Colored by Color Scripter

cs

#. Code_v2

visited 배열을 2차원으로 해결한 코드이다.

boolean 자료형 배열로 방문만 처리하는 것이 아니라

int 자료형 배열로 방문을 할 때,

벽을 몇 번 부순 상태에서 방문을 했는지 기록해두는 방법이다.

그리하여 나중에 그 좌표를 다시 방문했을 때,

더 적은 횟수로 벽을 부수고 온 적이 있다면 pass 해주었다.

이 방법은 한 칸씩 점점 퍼지는 방식으로 이동해서 가능한 방법인데

말이 되고픈 원숭이처럼 먼저 멀리 뛰쳐나갔을 경우에는 적용이 안되는것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ14442_v2 {
     
    static int N, M, K, res = -1, map[][], visited[][];
    static int[] dx = { 1, -1, 0, 0 }, dy = { 0, 0, 1, -1 };
 
    static class pos {
        // x좌표, y좌표, 지금까지 거리, 벽을 부순 횟수
        int x, y, dist, crush;
 
        public pos(int x, int y, int dist, int crush) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.crush = crush;
        }
    }
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken()); // 세로
        M = Integer.parseInt(st.nextToken()); // 가로
        K = Integer.parseInt(st.nextToken()); // 부술 수 있는 횟수
        map = new int[N][M];
        visited = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
                // 벽을 부순 횟수를 저장하는 visited 배열을 큰 값으로 초기화
                visited[i][j] = Integer.MAX_VALUE;
            }
        }
 
        Queue<pos> q = new LinkedList<>();
        visited[0][0] = 0;
        // 시작 칸과 끝나는 칸도 거리에 포함
        q.add(new pos(0, 0, 1, 0));
 
        while (!q.isEmpty()) {
            pos now = q.poll();
            // 목적지에 도착
            if(now.x == N-1 && now.y == M-1) {
                res = now.dist;
                break;
            }
            // 상하좌우로 탐색
            for (int d = 0; d < 4; d++) {
                int xx = now.x + dx[d];
                int yy = now.y + dy[d];
                // 범위를 벗어날 경우 pass
                if(xx < 0 || yy < 0 || xx >= N || yy >= M) continue;
                // 다음 칸으로 이동했을 때, 벽을 부순 횟수를 저장.
                // 다음 칸이 벽이면 벽을 부순 횟수가 1 증가할 것이고,
                // 벽이 아니라면 증가하지 않을 것임
                int nextK = now.crush + map[xx][yy];
                // K번을 초과하여 벽을 부순 상태이거나,
                // 더 적은 횟수로 벽을 부순 적이 있다면 pass
                if(nextK > K || visited[xx][yy] <= nextK) continue;
                
                visited[xx][yy] = nextK;
                q.add(new pos(xx, yy, now.dist + 1, nextK));
            }
        }
        
        System.out.println(res);
    }
}