티스토리 뷰
문제
- 0 이동가능 1이동불가능
- (0,0)에서 (N-1, M-1)위치까지가는 최단경로를 구하라 (최단경로가 없으면 -1)
- 최단경로는 시작하는칸(0,0)과 끝나는칸(N-1, M-1)을 포함한다. (최소 2 이상임)
- 💥 한개의 1을 0으로 바꾸어 사용 가능함. 💥
- 최대 맵의 크기는 1000*1000 임 1,000,000
문제 해결 방법 찾기
1. N행 M열의 그래프에 최단경로를 구하기 위한 BFS를 돌린다면 시간복잡도는 얼마나 걸리는가?
- 모든 정점은 N_M개 이고, 각 정점에 간선은 4개씩 있다.
- 한번 지나간 정점은 표기를 해두어 여러번 지나가지 않도록 한다.(방문체크)
- 모든 정점을 지나는 시간 + 모든 간선을 확인하는 시간 = N_M + 4_N_M 인데 상수배는 무시할 수 있으므로 N*M의 시간복잡도를 가진다.
2. 모든 1에 대해 0으로 바꾸었을 때의 최단경로를 BFS로 구한다면 시간복잡도는 얼마나 걸리는가?
- 1의 갯수는 최대 N_M개 이다. BFS를 한번 돌리는 시간복잡도는 N_M이므로, 모든1에 대해 BFS로 최단경로를 구한다면 (N_M)^2의 시간복잡도를 가진다.
- 주어진 시간은 2초 이므로 약 2억번 계산가능하고, (1000_1000)^2는 2억이 넘으므로 모든 1에 대해 최단경로를 구해 비교하는 방법은 불가능하다.
3. BFS에서 이동가능한 간선을 조사할때 새로운 조건을 추가하는 방법을 사용해보자.
- 지금까지는 행과열과 이동가능성(1/0)을 이용해서 이동할 간선을 조사했다면, 이번에는 벽을부순여부(1/0)를 추가해서 이동할 간선을 조사하자.
- 현재 정점에서 연결되어있는 정점들은 4개의 상태를 가질것이다. '1. 이동가능한곳(0)-벽을안부심(0)' , '2. 이동가능한곳(0)-벽을부심(1)', '3. 이동불가능(1)-벽을안부심(0)','4. 이동불가능(1)-벽을부심(1)' 이 중 1번,2번,3번은 큐에 넣어 추가이동이가능한데, 4번은 더이상 이동이 불가능하다.
- 방문체크 또한 원래는 어떤 정점에 대해서만 체크를 했지만, 정점이 벽을부신지 안부신지에 대해서도 체크를 해주어야 한다. 왜냐하면, 안그러면 벽을 부신경우와 안부신경우 둘다 조사를 해야하기 때문이죵
4. 또 중요한것이 방문체크를 언제하느냐가 중요한데.. 방문체크를 큐에 넣을때 할수도있고, 큐에서 뺄때 할수도 있는데 .. 무조건 큐에 넣을때 해줘야한다. 왜냐하면 큐에서 뺄때하면 큐에 중복값이 너무 많이 들어가버려서 메모리초과가 날수 있기 때문임..
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int[] mx = {0,0,1,-1};
static int[] my = {1,-1,0,0};
static int N,M,ans=-1;
static char[][] map;
static boolean[][][] check;
static class Node{
int i,j;
int broken;
int length;
public Node(int i, int j, int broken, int length){
this.i = i;
this.j = j;
this.broken = broken;
this.length = length;
}
}
static boolean range(int i, int j){
if(0<=i && i<N && 0<=j && j<M) return true;
return false;
}
static void bfs(int i, int j){
Queue<Node> q = new LinkedList<>();
q.add(new Node(i,j,0,1));
check[i][j][0] = true;
while(!q.isEmpty()){
Node t = q.poll();
//도착여부체크
if(t.i==N-1&&t.j==M-1){
ans = t.length;
return;
}
//인접노드조사
for(int n=0; n<4; n++){
int ni = t.i + mx[n];
int nj = t.j + my[n];
//유효범위안인지 체크
if(range(ni, nj)){
char mp = map[ni][nj];
//이동가능-벽부심
if(mp=='0'&&t.broken==1&&!check[ni][nj][1]){
q.add(new Node(ni,nj,t.broken,t.length+1));
check[ni][nj][t.broken]=true;
}
//이동가능-벽안부심
else if(mp=='0'&&t.broken==0&&!check[ni][nj][0]){
q.add(new Node(ni,nj,t.broken,t.length+1));
check[ni][nj][t.broken]=true;
}
//이동불가능-벽부심
else if(mp=='1'&&t.broken==0&&!check[ni][nj][1]){
q.add(new Node(ni,nj,1,t.length+1));
check[ni][nj][1]=true;
}
}
}
}
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stz = new StringTokenizer(br.readLine());
N = Integer.parseInt(stz.nextToken());
M = Integer.parseInt(stz.nextToken());
//map 입력받기
map = new char[N][M];
check = new boolean[N][M][2];
for(int i=0 ;i<N; i++){
map[i]=br.readLine().toCharArray();
}
bfs(0,0);
System.out.println(ans);
}
}