BOJ 2206 벽 부수고 이동하기

 

2206번: 벽 부수고 이동하기

주의해야 할 점

* 벽을 부쉈지만 최단경로가 아닌 경로와, 벽을 부수지 않는 최단 경로에서 경로가 서로 겹칠 경우, 제대로된 최단 경로를 구할 수 없게 된다. 이를 꼭 신경써주어야 한다.

 

해당 문제는 bfs를 사용하지만, 큐에 넣을 요소들이 더 추가되었고, 방문 내역을 저장하는 visit 배열이 true false 가 아니라, int 형으로 선언을 해서 해당 노드가 벽을 부순 경로에 포함되는지, 벽을 부수지 않아본 경로에 포함되는지 여부를 알려주도록 한다. 

 

따라서 상하좌우에 위치한 노드가 벽을 부순 경로에 포함되지만, 현재 큐에서 뽑은 값이 벽을 부수지 않은 경로에 포함 된다면, 상하좌우에 위치한 노드를 벽을 부수지 않은 경로에 포함 시키도록 한다.

이는 또한, 상하좌우에 위치한 노드가 벽을 부수지 않은 경로에 포함되지만, 현재 큐에서 뽑은 값이 벽을 부순 경로에 포함 된다면, 상하좌우에 위치한 노드를 그냥 그 상태로 두도록 한다.

이래야만 추후에 최단경로를 올바르게 구할 수 있다.

(벽을 부수지 않은 경로에도 포함되고 부순경로에도 포함되는 노드를 벽을 부섰다고 갱신해주면 , 이 후에 이 부수지 않은 경로에서 벽이 나오면 벽을 부술 수 없게된다.)

 

따라서 조건은

if (visit[nx][ny] <= tmp.wall ) continue;  

 이렇게 된다. 여기서 visit[nx][ny] == tmp.wall은 평범한 bfs에서처럼 이미 특정 경로를 통해서 visit 된 경로를 말하게 된다. (1 1 이거나 0 0 일 때) 

 

전체 자바 소스코드이다.

class pair
{
	int x;
	int y;
	int dis; //거리
	int wall; //벽 뚫었는가 
	
	pair(int x,int y , int dis, int wall){
		this.x=x;
		this.y=y;
		this.dis=dis;
		this.wall=wall;
	}
	
}


public class Main {
	static int N;
	static int M;
	static int[]dx = {-1,1,0,0};
	static int[]dy= {0,0,-1,1};
	static int[][]map;
	static int[][]visit;
	static int ans;
	public static void main(String[] args)
	{
        Scanner sc = new Scanner(System.in);	
		N = sc.nextInt();
		M = sc.nextInt();
		String s;
		map=new int[N][M];
		visit=new int[N][M];
		for(int i=0; i<N; i++) {
			s=sc.next();
			for(int j =0; j<M; j++) {
			map[i][j]=s.charAt(j)-'0';
			visit[i][j]=Integer.MAX_VALUE;
			}
		}
		ans=Integer.MAX_VALUE;
		bfs();
		if(ans==Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(ans);
		}
	
	}
	
	public static void bfs() {
		Queue<pair>q = new LinkedList<>();
		q.add(new pair(0,0,1,0));
		visit[0][0]=0;
		while(!q.isEmpty()) {
			pair tmp = q.poll();
			int x = tmp.x;
			int y =tmp.y;
			if(x==N-1 && y==M-1) {
				ans = tmp.dis;
				break;
			}
			for(int i=0; i<4 ; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx < 0 || ny <0 || nx >= N || ny >= M) continue;
				
				if(tmp.wall >= visit[nx][ny])continue;
				//벽이 없는 경로에서 나왔다면, 벽이 없는 경로의 wall 횟수로 저장해둔다.
				//나중에 벽없는 경로와 벽있는 경로의 중복을 허용하기 위해서 
				//반대로 생각하면, 벽이 있는 경로에서 나온 노드는 벽이 없는 경로의 wall횟수로 다시 저장될 수 있음.
				
				
				if(map[nx][ny]==0) { //벽이 아닐 때 , 벽이 없는 경로에서 지나친적 없을 때 
					q.add(new pair(nx, ny, tmp.dis+1, tmp.wall));  //distance만 늘려준다.
					visit[nx][ny]=tmp.wall; //저장 
				}
				else { //벽일 때 
					if(tmp.wall==0) { //벽을 이미 뚫은적 없을 때, 뚫은적 있다면 다시  뚫지 않아준다. (큐에 저장 X) 
						q.add(new pair(nx, ny, tmp.dis+1, tmp.wall+1)); //distance와 wall만 저장 
						visit[nx][ny]=tmp.wall+1;
					}
				}
			}
			
		}
	}
}