코딩 테스트(Coding Test)/백준
[백준] 2206번 : 벽 부수고 이동하기 - 자바(Java)
다문다뭉
2024. 11. 9. 16:37
Problem 🔒
문제
https://www.acmicpc.net/problem/2206
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
더보기
예제 입력 1
6 4
0100
1110
1000
0000
0111
0000예제 출력 1
15예제 입력 2
4 4
0111
1111
1111
1110예제 출력 2
-1
Approach ❌
벽 부술 자리를 조합으로 고르는 방법
- N, M이 최대 1000이므로 연산이 최대 100010001000=1000000000(10억)번이다.
- 배열을 다 도는 경우 1000*1000
- 벽을 고르는 경우의 수 999가지(약 1000가지)
- 컴퓨터는 1초에 대략 1억번 연산이 가능하기 때문에, 시간 초과가 난다.
Approach ⭕
BFS 탐색 시 사용하는 방문배열을 3차원으로 만들어서 벽을 부수지 않은 경우, 벽을 부순 경우 2가지로 나눠서 최단거리를 구할것이다.
- BFS를 활용한 탐색
- 큐에 (행, 열, 벽을 부쉈는지 여부(0,1)) 3가지 상태를 함께 저장하고 방문 체크한다.
- 출발 지점(0,0,0) 방문 처리하고, 큐에 출발 지점을 추가한다.
- 큐에서 위치를 꺼내 상,하,좌,우를 탐색하며 벽을 부수지 않았으면 벽을 부수고 이동할 수 있는지, 벽을 부수지 않고 이동할 수 있는지 확인한다.
- 벽을 부수고 이동하기 전에 방문 했는지 확인할 때, 벽을 부순 방문 배열에서 확인을 해야한다.
- 벽을 부수지 않았다면 벽을 부수고 이동할 수 있으며, 벽을 부쉈다는 상태로 바꿔서 큐에 추가한다.
- 큐가 비었을 때 목표 지점에 도달했는지 확인
- 벽을 부수지 않고 도달한 거리, 벽을 부수고 도달한 거리를 비교하여 출력한다.
- 두 값이 모두 0이면 -1을 출력한다.
- 한 쪽 값이 0이면, 다른 값을 출력한다.
- 둘 다 0이 아니라면, 최단 거리를 출력한다.
Solution 💡
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 벽부수고이동하기 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N=sc.nextInt(), M=sc.nextInt(), dr[]={-1,1,0,0}, dc[]={0,0,-1,1};
int[][] map = new int[N][M];
int[][][] visit = new int[N][M][2]; //[r][c][0]:벽 부수지 않고 이동한 경우, [r][c][1]:벽 1개 부수고 이동한 경우
Queue<int[]> q = new LinkedList<>();
for(int i=0; i<N; i++){
String str = sc.next();
for(int j=0; j<M; j++){
map[i][j]= str.charAt(j) - '0';
}
}
visit[0][0][0] = 1;
q.add(new int[]{0,0,0});
while(true){
int[] get = q.poll();
int r = get[0];
int c = get[1];
int broken = get[2];
for(int d=0; d<4; d++){
int nr = r + dr[d];
int nc = c + dc[d];
if(nr>=0 && nr<N && nc>=0 && nc<M){
// 1. 벽이고, 부순 적 없고, 방문한 적 없으면
// 벽을 부순 방문배열에서 방문 체크!
if(map[nr][nc]==1 && broken==0 && visit[nr][nc][1]==0){
visit[nr][nc][1] = visit[r][c][0] + 1;
q.add(new int[]{nr,nc,1});
}
// 2. 벽이 아니고, 방문한 적 없으면
else if(map[nr][nc]==0 && visit[nr][nc][broken]==0){
visit[nr][nc][broken] = visit[r][c][broken] + 1;
q.add(new int[]{nr,nc,broken});
}
}
}
if(q.isEmpty()){
int zero = visit[N-1][M-1][0];
int one = visit[N-1][M-1][1];
System.out.println((zero+one == 0)?-1:(zero*one==0)?Math.max(zero,one):Math.min(zero,one));
break;
}
}//while
}
}BFS는 재귀없이 탐색하는데 어떻게 모든 경우의 수를 탐색할 수 있을까?
- 결론적으로 모든 경우의 수를 탐색하지 않는다.
- 큐에 (행, 열, 벽을 부쉈는지 여부(0,1)) 3가지 상태를 함께 저장하고 방문 체크한다.
- 인접한 자리가 방문된 자리는 이미 최단 경로로 방문한 곳이다!!
- 큐에 시작점 (0,0,0)을 넣고 방문 표시하고 BFS를 진행한다.
- 큐에서 (0,0,0)을 꺼내고 상,하,좌,우 인접한 칸을 확인한다.
- 인접한 자리(1,0)가 벽이고 현재 벽을 부순 경우는 없으니, 벽을 부수고 이동한다.
- 벽을 부순 상태 배열에 방문 체크를 하고 큐에 (1,0,1)를 추가한다.
- 인접한 자리(0,1)가 빈 칸이므로 벽을 부수지 않고 이동한다.
- 벽을 부수지 않은 상태 배열에 방문 체크를 하고 큐에 (0,1,0)을 추가한다.
- 인접한 자리(1,0)가 벽이고 현재 벽을 부순 경우는 없으니, 벽을 부수고 이동한다.
- 큐에서 (1,0,1)을 꺼내고 상,하,좌,우 인접한 칸을 확인한다.
- 현재 벽을 부순 적이 있고, 인접한 자리(2,0), (1,1)가 벽이므로 이동하지 못한다.
- 큐에서 (0,1,0)을 꺼내고 상,하,좌,우 인접한 칸을 확인한다.
- 현재 벽을 부순 적이 없고, 인접한 자리(1,1)가 벽이므로 벽을 부수고 이동한다.
- 벽을 부순 상태 배열에 방문 체크를 하고 큐에 (1,1,1)을 추가한다.
- 인접한 자리(0,2)가 빈 칸이므로 벽을 부수지 않고 이동한다.
- 벽을 부수지 않은 상태 배열에 방문 체크를 하고 큐에 (0,2,0)을 추가한다.
- 현재 벽을 부순 적이 없고, 인접한 자리(1,1)가 벽이므로 벽을 부수고 이동한다.
알게된 점 😯
- char를 int로 변환하는 방식 str.charAt(j) - '0’
- String 문자열에서 j번째 인덱스 문자를 반환한다.
- ‘0’은 문자 0이고, char 타입에서 문자는 유니코드 값으로 저장되어, ‘0’의 값은 48이다.
- 유니코드 값에서 유니코드 값(48)을 빼면 간단하게 정수 값을 얻을 수 있다.