문제 확인 -> https://www.acmicpc.net/problem/2206
해당 문제는 BFS(너비 우선 탐색) 알고리즘을 활용한 응용 문제이며,
지도를 문자열로 입력 받아 '0' 이면 이동 가능한 좌표, '1' 이면 벽을 의미하며,
주인공은 최대 1번 벽을 뚫을 수 있고, 이를 모두 고려하여 목적지까지 최단 거리를 구해야 합니다.
BFS 로 문제를 해결하는 것은 동일하지만, visited (방문) 배열값을 설정하는 과정에서 3차원 배열을 사용합니다.
3차원 배열을 설정한 이유는, 벽을 한 번도 뚫지 않고 최단 거리로 도달하는 경우, 한 번 뚫고 최단 거리로 도달하는 경우 2가지가 존재하기 때문입니다.
- int visited[y][x][2]
- z index 값이 0 인 경우, 벽을 이미 1번 뚫은 경우 해당 지점까지의 최단 거리
- z index 값이 1 인 경우, 벽을 한번도 뚫지 않고 해당 지점까지의 최단 거리
최종 결과값 산출 과정에서, 위 3차원 배열에서의 0보다 큰 최소값을 return 값으로 설정하며,
최종 지점에 도달하지 못한 경우에는 -1 을 return 합니다.
참고로, 이 문제는 메모리 초과가 발생할 수 있는데 Queue 에 Node 를 넣기 전에 미리 방문 지점에 최단 거리 값을 설정해야 합니다.
그렇지 않은 경우에는 메모리 초과가 발생할 수 있습니다.
여러 시도 끝에 성공한 코드는 아래와 같습니다. (이 문제는 여러 시행착오를 거칠 수 있으며 질문 검색 게시판을 통해 힌트를 찾으시면서 해결하는 것을 권장합니다)
code
import java.io.*;
import java.util.*;
class Main {
static class Node {
int x;
int y;
int depth;
int count;
Node (int _x, int _y, int _depth, int _count) {
x = _x;
y = _y;
depth = _depth;
count = _count;
}
}
public static String miro[];
public static int visited[][][];
public static int height;
public static int width;
public static int bfs(int n, int m) {
try {
Queue<Node> q = new LinkedList<>();
q.add(new Node(n,m,1,1));
while (!q.isEmpty()) {
Node node = q.poll();
if (node.y == height-1 && node.x == width-1) {
int count = Integer.MAX_VALUE;
if (visited[height-1][width-1][0] > 0) {
count = visited[height-1][width-1][0] < count ? visited[height-1][width-1][0] : count;
}
if (visited[height-1][width-1][1] > 0) {
count = visited[height-1][width-1][1] < count ? visited[height-1][width-1][1] : count;
}
return count;
}
if (node.x-1 >= 0 && node.x-1 <width) {
// 가려는 곳이 벽 and 벽을 한 번도 안 뚫은 경우
if (miro[node.y].charAt(node.x-1) == '1' && node.count > 0 && visited[node.y][node.x-1][node.count-1] == 0) {
visited[node.y][node.x-1][node.count-1] = node.depth + 1;
q. add(new Node(node.x-1,node.y,node.depth+1, node.count-1));
} else if (miro[node.y].charAt(node.x-1) == '0' && visited[node.y][node.x-1][node.count] == 0){
// 가려는 곳이 벽이 아님
visited[node.y][node.x-1][node.count] = node.depth + 1;
q. add(new Node(node.x-1,node.y,node.depth+1, node.count));
}
}
if (node.x+1 >= 0 && node.x+1 <width) {
// 가려는 곳이 벽 and 벽을 한 번도 안 뚫은 경우
if (miro[node.y].charAt(node.x+1) == '1' && node.count > 0 && visited[node.y][node.x+1][node.count-1] == 0) {
visited[node.y][node.x+1][node.count-1] = node.depth + 1;
q. add(new Node(node.x+1,node.y,node.depth+1, node.count-1));
} else if (miro[node.y].charAt(node.x+1) == '0' && visited[node.y][node.x+1][node.count] == 0){
// 가려는 곳이 벽이 아님
visited[node.y][node.x+1][node.count] = node.depth + 1;
q. add(new Node(node.x+1,node.y,node.depth+1, node.count));
}
}
if (node.y-1 >= 0 && node.y-1 < height) {
// 가려는 곳이 벽 and 벽을 한 번도 안 뚫은 경우
if (miro[node.y-1].charAt(node.x) == '1' && node.count > 0 && visited[node.y-1][node.x][node.count-1] == 0) {
visited[node.y-1][node.x][node.count-1] = node.depth + 1;
q. add(new Node(node.x,node.y-1,node.depth+1, node.count-1));
} else if (miro[node.y-1].charAt(node.x) == '0' && visited[node.y-1][node.x][node.count] == 0){
// 가려는 곳이 벽이 아님
visited[node.y-1][node.x][node.count] = node.depth + 1;
q. add(new Node(node.x,node.y-1,node.depth+1, node.count));
}
}
if (node.y+1 >= 0 && node.y+1 < height) {
// 가려는 곳이 벽 and 벽을 한 번도 안 뚫은 경우
if (miro[node.y+1].charAt(node.x) == '1' && node.count > 0 && visited[node.y+1][node.x][node.count-1] == 0) {
visited[node.y+1][node.x][node.count-1] = node.depth + 1;
q. add(new Node(node.x,node.y+1,node.depth+1, node.count-1));
} else if (miro[node.y+1].charAt(node.x) == '0' && visited[node.y+1][node.x][node.count] == 0){
// 가려는 곳이 벽이 아님
visited[node.y+1][node.x][node.count] = node.depth + 1;
q. add(new Node(node.x,node.y+1,node.depth+1, node.count));
}
}
}
} catch (Exception e) {
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
height = Integer.parseInt(input[0]);
width = Integer.parseInt(input[1]);
miro = new String[height];
visited = new int[height][width][2];
visited[0][0][0] = 1;
visited[0][0][1] = 1;
for (int i = 0; i < height; i++) {
miro[i] = br.readLine();
}
System.out.printf("%d\n", bfs(0,0));
}
}