[BOJ] 1938.통나무 옮기기(BFS).java

#. Problem

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

* 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

통나무를 열심히 옮겨보는 BFS + 시뮬레이션 문제이다.

주요 조건을 살펴보면

* 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.

* 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전

* 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 3*3 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다.

문제의 이해는 간단할 수 있지만, 

구현해내는 구현력이 중요할 것 같다.

시간 복잡도는 2(가로 or 세로) * N^2 이므로

대략적으로 O(N^2) 이 나온다.

#. Code

통나무의 중심 좌표와 방향(가로 or 세로)을 들고 이동하였다.

시뮬레이션 문제는 중간에 삐끗하면 어디가 틀린지 찾아내기가 힘들다ㅠ.ㅠ

멘붕의 상태에서 더덕분 발견하기는 쉽지 않았다.

문제를 재정의하고 요약하는 과정에서

동작 계획을 잘 세워놓는게 정말 중요하다 !!

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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188

import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue;   public class BOJ1938 {       static int N;     static char map[][];     static Point[] BP, EP;     static int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };       static class State {         int x, y, dir, dist;           public State() {             super();         }           State(int x, int y, int dir, int dist) {             this.x = x;             this.y = y;             this.dir = dir; // 0: 가로, 1 : 세로             this.dist = dist;         }       }       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           N = Integer.parseInt(br.readLine());         map = new char[N][N];         // 처음위치와 최종위치의 좌표         BP = new Point[3];         EP = new Point[3];           int bi = 0, ei = 0;         for (int i = 0; i < N; i++) {             map[i] = br.readLine().toCharArray();             // 처음위치와 최종위치를 저장             for (int j = 0; j < N; j++) {                 if (map[i][j] == 'B')                     BP[bi++] = new Point(i, j);                 if (map[i][j] == 'E')                     EP[ei++] = new Point(i, j);             }         }           System.out.println(bfs());     }       private static int bfs() {           // 통나무가 가로로 있을 경우와 세로로 있을 경우 이동 상태         boolean[][][] visited = new boolean[2][N][N];         Queue<State> q = new LinkedList<>();           // 통나무 상태 확인         int dir = 0;         // 통나무가 가로로 있다면         if (BP[0].y + 1 == BP[1].y) dir = 0;         else dir = 1;           // B의 중심 기준으로 이동         q.add(new State(BP[1].x, BP[1].y, dir, 0));         visited[dir][BP[1].x][BP[1].y] = true;           while (!q.isEmpty()) {               State now = q.poll();             // B의 중심이 E의 중심에 도달하면             if (now.x == EP[1].x & now.y == EP[1].y) {                 // 통나무가 가로 방향으로 있고 도작 지점도 가로                 if (now.dir == 0 && map[now.x][now.y - 1] == 'E' && map[now.x][now.y + 1] == 'E') {                     return now.dist;                 }                 // 통나무가 세로방향으로 있고 도착 지점도 세로                 else if (now.dir == 1 && map[now.x - 1][now.y] == 'E' && map[now.x + 1][now.y] == 'E'){                     return now.dist;                 }             }               // 4방으로 이동             for (int d = 0; d < 4; d++) {                 int xx = now.x + dx[d];                 int yy = now.y + dy[d];                                  // 통나무가 가로일 경우                 if(now.dir == 0) {                     // 이동할 수 있는 확인                     if(!checkHoriz(xx, yy, d)) continue;                  }                 // 통나무가 세로일 경우                 else {                     // 이동할 수 있는 확인                     if(!checkVerti(xx, yy, d)) continue;                  }                                  // 이미 방문한 곳이라면 pass                 if (visited[now.dir][xx][yy]) continue;                   visited[now.dir][xx][yy] = true;                 q.add(new State(xx, yy, now.dir, now.dist + 1));             }               // 회전이 가능한지 체크             if (canRotation(now.x, now.y)) {                 // 통나무가 가로인 경우                 if (now.dir == 0 && !visited[1][now.x][now.y]) {                     visited[1][now.x][now.y] = true;                     q.add(new State(now.x, now.y, 1, now.dist + 1));                 }                 // 통나무가 세로인 경우                 else if (now.dir == 1 && !visited[0][now.x][now.y]) {                     visited[0][now.x][now.y] = true;                     q.add(new State(now.x, now.y, 0, now.dist + 1));                 }             }           }           return 0;     }       private static boolean checkVerti(int xx, int yy, int d) {                  // 상/하로 이동         if (d < 2) {             // 통나무 끝이             // 범위를 넘어가면 pass             if (xx - 1 < 0 || xx + 1 >= N) return false;             // 나무가 있을 경우             if (map[xx][yy] == '1' || map[xx - 1][yy] == '1' || map[xx + 1][yy] == '1') return false;         }         // 좌/우로 이동         else {             // 통나무 끝이             // 범위를 넘어가면 pass             if (yy < 0 || yy >= N) return false;             // 나무가 있을 경우             if (map[xx][yy] == '1' || map[xx - 1][yy] == '1' || map[xx + 1][yy] == '1') return false;         }                  return true;     }       private static boolean checkHoriz(int xx, int yy, int d) {                  // 상/하로 이동         if (d < 2) {             // 통나무 끝이             // 범위를 넘어가면 pass             if (xx < 0 || xx >= N) return false;             // 나무가 있을 경우             if (map[xx][yy] == '1' || map[xx][yy-1] == '1' || map[xx][yy+1] == '1') return false;         }         // 좌/우로 이동         else {             // 통나무 끝이             // 범위를 넘어가면 pass             if (yy - 1 < 0 || yy + 1 >= N) return false;             // 나무가 있을 경우             if (map[xx][yy] == '1' || map[xx][yy - 1] == '1' || map[xx][yy + 1] == '1') return false;         }                  return true;     }       private static boolean canRotation(int x, int y) {           for (int i = x - 1; i <= x + 1; i++) {             for (int j = y - 1; j <= y + 1; j++) {                 // 범위를 나갈경우                 if (i < 0 || j < 0 || i >= N || j >= N) return false;                 // 나무가 있을 경우                 if (map[i][j] == '1') return false;             }         }           return true;     }   }   Colored by Color Scripter

cs