BFS를 응용해보자
✅ 문제 설명
0은 길, 1은 벽이다.
벽을 1개만 부술 수 있을 때, (0,0) 에서 우측 하단까지 도달하는 최단 거리를 구해야 한다.
한 칸씩 이동하며 최단 거리를 찾고 있으므로 "bfs" 문제이다.
그렇다면 가장 간단한 방법은 벽을 1개씩 다 부숴보면서 bfs를 매번 확인하는 것이다.
하지만, 이 방법은 시간이 오래 걸린다.
우리는 bfs를 1번만 돌면서 해결할 것이다.
✅ 아이디어
- Queue에 넣을 데이터가 무엇인가?
- 방문 체크를 어떻게 할 것인가?
1. Queue에 넣을 데이터가 무엇인가?
현재 좌표에서 다음 좌표로 이동할 때 필요한 데이터는 다음과 같다.
즉, 아래의 데이터를 큐에 넣고 돌아다닌다.
- 다음 좌표 행, 열
- (0,0)에서 다음 좌표까지의 거리
- 지금까지 몇 개의 벽을 부쉈는지 (그래야 다음 좌표가 벽일 경우 벽을 더 부술 수 있는지 확인할 수 있음)
2. 방문 체크를 어떻게 할 것인가?
해당 좌표에 벽을 부수고 도착한건지, 안부수고 도착한건지에 따라 같은 좌표도 재방문할 수 있다. 왜냐하면 벽을 부수고 그 좌표에 갈 수도 있고, 벽을 안부수고 그 좌표에 갈 수 있는데 최단 거리가 다르기 때문이다.
검은점에서 파란점까지 파란길처럼 돌아갈 수 있지만, 벽을 부수고 빨간길처럼 더 빨리 갈 수 있다. 그러니까 파란점을 2번 방문하게 될 수 있는 것이다.
그럼 무조건 더 빠른, 빨간길이 좋을까?
그렇지 않다. 최단 거리도 끝에 도달하고 봐야한다.
만약 끝에 가기 위해 1개의 벽을 더 부숴야 했다면 파란길이 정답이 될 것이다.
이러한 상황을 고려하기 위해 방문 체크를 위한 배열을 3차원으로 관리한다.
해당 좌표까지 벽을 몇 개 부숴서 도달했던 것인지 확인해야 하기 때문이다.
예를 들어,
- visit[3][4][0]은 좌표 (3,4)에 지금까지 벽을 한 번도 부수지 않고 방문한 적 있는지 유무이다.
- visit[3][4][1]은 좌표 (3,4)에 지금까지 벽을 1개 부숴서 방문한 적 있는지 유무이다.
✅ 정답 코드
public class Main {
static final int[] dx = new int[] {-1,1,0,0};
static final int[] dy = new int[] {0,0,-1,1};
static final int ROAD = 0, WALL = 1;
static int N, M;
static int[][] map;
public static void main(String[] args) throws Exception {
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];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
char[] input = st.nextToken().toCharArray();
for(int j = 0; j < input.length; j++) {
map[i][j] = input[j] - '0';
}
}
int answer = -1;
boolean[][][] visit = new boolean[N][M][2];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[] {0, 0, 1, 0});
visit[0][0][0] = true;
visit[0][0][1] = true;
while(!q.isEmpty()) {
int[] now = q.poll();
int r = now[0];
int c = now[1];
int d = now[2];
int count = now[3];
if(r == N-1 && c == M-1) {
answer = d;
break;
}
for(int i = 0; i < dx.length; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if(nr<0 || nr>=N || nc<0 || nc>= M) continue;
if(visit[nr][nc][count]) continue;
if(map[nr][nc] == ROAD) {
visit[nr][nc][count] = true;
q.offer(new int[] {nr, nc, d+1, count});
}
if(map[nr][nc] == WALL && count < 1) {
visit[nr][nc][count+1] = true;
q.offer(new int[] {nr, nc, d+1, count+1});
}
}
}
System.out.print(answer);
br.close();
}
}참고) 클래스를 이용했던 이전 코드(정답)
- visit을 3차원으로 관리하지 않고 클래스에 정의해서 Map에 최단 거리와 방문 체크를 저장했던 코드이다.
- 중복이 많아 큐에 데이터를 저장하고, visit을 3차원으로 관리하는 방법으로 바꿨다.
public class Main {
static class Point {
int value;
int[] dist = new int[2]; // dist[0] : 벽을 0개 부쉈을때 올 수 있는 최단 거리
boolean[] visit = new boolean[2]; // visit[0] : 벽을 0개 부쉈을 때 이 좌표를 방문했는지
public Point(int value) {
this.value = value;
Arrays.fill(dist, Integer.MAX_VALUE);
}
}
static final int[] dx = new int[] {-1,1,0,0};
static final int[] dy = new int[] {0,0,-1,1};
static final int WALL = 1;
static int N, M;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
Point[][] map = new Point[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
char[] input = st.nextToken().toCharArray();
for(int j = 0; j < M; j++) {
map[i][j] = new Point(input[j] - '0');
}
}
map[0][0].dist[0] = 1;
map[0][0].dist[1] = 1;
int answer = Integer.MAX_VALUE;
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[] {0,0,1});
while(!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0];
int c = cur[1];
if(r==N-1 && c==M-1) {
answer = Math.min(answer, map[r][c].dist[1]);
break;
}
for(int i = 0; i < dx.length; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if(!(nr>=0 && nr<N && nc>=0 && nc<M)) continue;
Point next = map[nr][nc];
if(next.value == WALL && !next.visit[1]) { // 벽이었으면 부수고 간다
if(map[r][c].dist[0] < Integer.MAX_VALUE) {
map[nr][nc].dist[1] = map[r][c].dist[0] + 1;
q.offer(new int[] {nr, nc});
next.visit[1] = true;
}
}
if(next.value != WALL && !next.visit[0]) { // 길이고 벽을 부수지 않고 방문한적 없으면
if(map[r][c].dist[0] < Integer.MAX_VALUE) {
map[nr][nc].dist[0] = map[r][c].dist[0] + 1;
q.offer(new int[] {nr, nc});
next.visit[0] = true;
}
}
if(next.value != WALL && !next.visit[1]) {
if(map[r][c].dist[1] < Integer.MAX_VALUE) {
map[nr][nc].dist[1] = map[r][c].dist[1] + 1;
q.offer(new int[] {nr, nc});
next.visit[1] = true;
}
}
}
}
// for(int i = 0; i < N; i++) {
// for(Point pp : map[i]) {
// System.out.print(Arrays.toString(pp.dist));
// }
// System.out.println();
// }
if(answer == Integer.MAX_VALUE) answer = -1;
System.out.print(answer);
br.close();
}
}회고
- 두 코드 모두 정답이지만 나는 위에 코드가 좋다고 생각한다.
왜냐하면 최단거리와 방문체크를 Point[][] 라는 2차원 배열에 객체로 저장하니 map이라는 변수가 한 번에 많은 일을 하면서 이해하기 복잡해졌다. - 하지만 위에 코드도 개선의 여지가 남아있다. 큐에 int[]를 저장하면 이 배열에 크기가 얼마인지, 해당 인덱스가 무엇을 의미하는지 알 수 없기 때문이다. 따라서 큐에 int[]를 쓰는 것보다 큐에 담을 데이터를 클래스로 정의하는 것이 더 좋겠다.
- 고민 결과, 코딩 테스트는 빠르게 푸는 것도 중요하므로 우선은 클래스 정의 대신 int[]로 먼저 접근하기로 했다.
Java, JavaScript