접근
이 문제는 BFS 문제이다. 하지만 한가지 추가된 조건이 있는데
가지못하는 길을 한번 갈 수 있게 바꿀 수 있다.
그래서 가지 못하는 길을 한번 갈 수 있게 바꾼 여러 경로
그냥 갈 수 있는 길만 간 여러 경로들을 비교해서 가장 최단 경로를 발견하는 문제이다.
처음 나의 접근법은 아래와 같다.
- 아래 정보를 저장한다.
-map : 전체 0과 1이 저장된 NxM 행렬
-list : 1에 대한 정보가 저장된 list (벽에 대한 정보) - 처음에는 벽을 뚫지 않고 가는 최단 경로에 대한 값을 구한다. 즉, BFS() 호출
- 벽 데이터가 저장된 list의 값들을 하나씩 가져온다. 즉 1이 저장된 행렬에 대한 데이터를 가져와서 map과 일치하는 그 자리에 벽을 없앤다. 그리고 BFS() 호출하고 결과값이 돌아오면 다시 원상복구해준다.
즉 벽 데이터를 하나씩 허물어 보는 방법이다.
하지만 위의 방법은 시간 초과가 발생한다.
위 그림을 보면서 생각해보자. 만약 상황이 위와 같은 상황이라고
가정한다면
1) 벽 데이터를 하나씩 허무는 방법은 항상 벽을 허물지 않는 경우의 수도 같이 진행하고 있다. 그러면 벽을 허문다고 하더라도 BFS()의 결과는 벽을 허물지 않은 방법으로 도출된다.( 벽을 허물지 않은 방법을 벽이 존재하는 개수만큼 무의미하게 반복한다는 것이다. 처음 방법으로 진행한다면)
3) 벽 데이터를 하나씩 허무는 방법은 위 노란색으로 표시된 부분에 대한 중복된 경로가 발생한다는 것을 알 수 있다.
과정
따라서 하나씩 허무는 방법은 잘못되었다.
하나씩 허무는 것이 아니라 허물지 않는 방법과 한번 허무는 방법이 같은 레벨로 같이 나아가도록 하는 방법이 필요하다
위 문제의 경우 3차원의 visit 배열이 필요하다.
- visit[x][y][0] : 하나는 허물지 않고 그냥 가는 경우의 visit 배열
- visit[x][y][1] : 나머지는 하나를 허물고 가는 경우의 visit배열
이렇게 두개가 같이 나아가도록 하는 것이다.
같은 레벨로 같이 Queue에 넣을 것이다.
또한 한번만 허물기 때문에 Queue에 쌓이는 같은 레벨의 경로에 대해서 벽을 두번이상 허무는 경로에 대해서는 쌓이지 않도록 하는 조건을 넣어주어야 한다.
우리가 생각해볼 것은 BFS의 Queue의 역할을 생각해봐야 한다.
Queue에는 같은 레벨의 경로가 쌓이는 것이고
위 문제는 같은 레벨에 벽을 허무는 경우와 벽을 한번 허무는 경우가 같이 쌓여있는 것이다!
풀이
잘못된 접근법에 대한 풀이
import java.io.*;
import java.util.*;
public class Main{
static int N;
static int M;
static boolean[][] visit;
static boolean[][] map;
static ArrayList<XY> wall;
static int[] cx = {-1,1,0,0};
static int[] cy = {0,0,-1,1};
static class XY{
int x;
int y;
public XY(int x, int y){
this.x =x;
this.y=y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());// 행 1~1000
M = Integer.parseInt(st.nextToken());// 열 1~1000
visit = new boolean[N+1][M+1];
map = new boolean[N+1][M+1];
wall = new ArrayList<>();
for(int i=1;i<=N;i++){
String input = br.readLine();
for(int j=1;j<=M;j++){
int v = input.charAt(j-1)-'0';
if(v==0)
map[i][j] =true;
else{
map[i][j]=false;
wall.add(new XY(i,j));
}
}
}
int f_result = BFS();
int min = Integer.MAX_VALUE;
boolean tag = false;
for(int i=0;i<wall.size();i++){
//visit배열 모두 false로 만들어주기
for(boolean[] row : visit){
Arrays.fill(row,false);
}
XY xy = wall.get(i);
map[xy.x][xy.y]=true;
int output =BFS();
if(output>-1 && output<min ) {
tag=true;
min = output;
}
map[xy.x][xy.y]=false;
}
if(f_result==-1 && tag==true) bw.write(Integer.toString(min));
else if(f_result ==-1 && tag == false) bw.write("-1");
else if(f_result !=-1 && tag == true) {
if(f_result>min) bw.write(Integer.toString(min));
else bw.write(Integer.toString(f_result));
}
else if(f_result!=-1 && tag==false)bw.write(Integer.toString(f_result));
bw.flush();
bw.close();
br.close();
}
static int BFS(){
Queue<XY> Q = new LinkedList<>();
Q.offer(new XY(1,1));
visit[1][1]=true;
int cost=1;
boolean tag = false;
while(!Q.isEmpty()){
int size = Q.size();
for(int i=0;i<size;i++){
XY xy = Q.poll();
//N,M에 도착한 경우
if(xy.x==N && xy.y==M){
tag = true;
break;
}
// 상하좌우 전진하기 위한
for(int j=0;j<4;j++){
int x = cx[j]+xy.x;
int y = cy[j]+xy.y;
//조건문 map 배열에 벗어나지 않으면서 벽이 아니고 방문하지 않은
if(x>=1 && x<=N && y>=1 && y<=M && map[x][y]==true && visit[x][y]==false){
visit[x][y]=true;
Q.offer(new XY(x,y));
}
}
} //모든 Q 소진시 빠져나가는 for
if(tag==true) break;
cost++;
}
if(tag==false)
return -1;
else
return cost;
}
}허물지 않는 경로와
하나 허문 경로를 분리해서 같은 레벨로 진행되도록 한 경우의 풀이
import java.util.*;
import java.io.*;
public class Main{
static char[][] map;
static boolean[][][] visit;
static int result=0;
static int N;
static int M;
static int[] cx = {0,0,-1,1};
static int[] cy = {1,-1,0,0};
static class Road{
int x;
int y;
int cnt;
int wall; // 현재 어디에 속하는지
public Road(int x, int y, int cnt, int wall){
this.x=x;
this.y=y;
this.cnt = cnt;
this.wall = wall;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());//행 1~1,000
M = Integer.parseInt(st.nextToken());//렬 1~1,000
map = new char[N][M];
visit = new boolean[N][M][2];
//행렬 map 데이터 받기
for(int i=0;i<N;i++){
String input = br.readLine();
for(int j=0;j<M;j++){
map[i][j]=input.charAt(j);
}
}
BFS();
if(result ==0) bw.write("-1");
else bw.write(Integer.toString(result));
bw.flush();
bw.close();
br.close();
}
static void BFS(){
Queue<Road> Q = new LinkedList<>();
Q.offer(new Road(0,0,1,0));
visit[0][0][0] = true;
visit[0][0][1] = true;
while(!Q.isEmpty()){
int size = Q.size();
for(int i=0;i<size;i++){
Road r = Q.poll();
// 도달한 경우
if(r.x == N-1 && r.y==M-1){
result = r.cnt;
return;
}
//상하좌우
for(int j=0;j<4;j++) {
int x = r.x + cx[j];
int y = r.y + cy[j];
if(x<0 || x>=N || y<0 || y>=M) continue;
if(map[x][y]=='0' && visit[x][y][r.wall]==false){
visit[x][y][r.wall]=true;
Q.offer(new Road(x,y,r.cnt+1,r.wall));
}
if(map[x][y]=='1'){
if(visit[x][y][1]==false && r.wall==0){
visit[x][y][1]=true;
Q.offer(new Road(x,y,r.cnt+1,1));
}
}
} // 상화좌우 for
}//Q 도는 for
} //while
}
}정리
두개의 도화지가 있다고 생각하면 된다.
도화지 A로 가다가 장애물을 만나는 경우는 도화지 B로 옮겨서 그리는 것이다.
하지만 도화지 A 그리면서 장애물을 영원히 만나지 않는 경우는 그냥 A로 계속 그린다.
이렇게 도화지 A와 B를 분리한 이유는 도화지 A가 간 경로를 도화지B도 가게 하기 위해서다 만약에 하나의 도화지로만 진행하면 도화지 A가 간 경로는 이미 true이기 대문에 도화지 B는 갈 수 없다.
꾸준하게 Ready, Set, Go!