[알고리즘] 백준 > #2206. 벽 부수고 이동하기
문제링크
풀이방법
신기한 문제다! 벽을 한 번만 부술 수 있는데 이걸 어디에 어떻게 설정해서 알 수 있을까 생각했다. 보통 이차원 배열을 맵으로 사용하는데, 여기서는 한 차원을 더 뒀다. 삼차원 배열을 사용했다. [0][i][j]는 한 번도 벽을 부수지 않은 케이스를 다루고 [1][i][j]는 벽을 한 번 부순 상태를 다룬다. [i][j]에서 벽이 있는 곳을 마주하면 z값이 0인지 확인한다. 0이면 z를 1로 설정해 최소 값으로 해당 위치에 도달할 수 있는지 확인하는 방식이다. z가 1이면 이미 한 번 벽을 부쉈기 때문에 어떤것도 하지 않는다!
코드
class Solution2206 {
private final int[] dy = {0, 0, +1, -1};
private final int[] dx = {+1, -1, 0, 0};
private final int NOT_VISITED = 10000000;
private int n, m;
private int[][] map;
Solution2206(int n, int m, int[][] map) {
this.n = n;
this.m = m;
this.map = new int[n][m];
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) this.map[i][j] = map[i][j];
}
int searchShortestPath() {
int[][][] count = new int[2][n][m];
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
count[0][i][j] = NOT_VISITED;
count[1][i][j] = NOT_VISITED;
}
Queue<Triple> q = new LinkedList<>();
q.offer(new Triple(0, 0, 0));
count[0][0][0] = 1;
while (!q.isEmpty()) {
Triple head = q.poll();
for (int d = 0; d < 4; d++) {
int nextY = head.y + dy[d];
int nextX = head.x + dx[d];
if (!isInRange(nextY, nextX)) continue;
int nextZ;
if (map[nextY][nextX] == 0) nextZ = head.z;
else if (head.z == 0) nextZ = 1;
else continue;
if (count[nextZ][nextY][nextX] > (count[head.z][head.y][head.x] + 1)) {
count[nextZ][nextY][nextX] = count[head.z][head.y][head.x] + 1;
q.offer(new Triple(nextZ, nextY, nextX));
}
}
}
int shortestPath = Math.min(count[0][n - 1][m - 1], count[1][n - 1][m - 1]);
return shortestPath != NOT_VISITED ? shortestPath : -1;
}
private boolean isInRange(int y, int x) {
return ((y >= 0) && (y < n) && (x >= 0) && (x < m));
}
}
class Triple {
int z, y, x;
Triple(int z, int y, int x) {
this.z = z;
this.y = y;
this.x = x;
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 > #2206. 벽 부수고 이동하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-2206.-벽-부수고-이동하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)