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

#. Problem

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

* 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. 맵을 이동하면서 좌표와 벽을 부순 횟수, 지금까지의 거리를 같이 들고 다녀야 한다.

   벽을 부수지 않고 방문한 체크 배열과 벽을 한 번 부수고 방문한 체크 배열이 필요하다.

2. 다음은 흔한 상하좌우 탐색을 하는데,

   다음 좌표가 벽이 아닐 경우와 벽일 경우로 나누어서 생각해보아야 한다.

   각 단계에서 이미 방문했을 경우 pass 시켜주고

   이동할 수 있는 상태라면 queue에 넣어주자.

#. 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

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 BOJ2206 {       static int N, M, 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()); // 가로         map = new int[N][M];         visited = new boolean[N][M][2];           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<>();         // 시작 칸과 끝나는 칸도 거리에 포함         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];                                  // 범위를 벗어날 경우                 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 {                     // 벽을 부술 수 없거나, 이미 왔던 길일 경우 pass                     if(now.k != 0 || 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