[백준 2206] - 벽 부수고 이동하기(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

---

[문제 풀이]

최단 경로를 찾는 BFS로 해결할 수 있다. 만약 모든 벽을 0으로 바꾸고 찾게 된다면 N과 M 제한 조건에 의해

(1000*1000)^2의 복잡도를 가지게 되어 시간 초과가 된다.

이 문제의 핵심은 벽을 부수고 이동하는 것이 빠르면, 벽을 한 개 까지 부수고 이동하여도 된다 라는 조건이 있다.

즉 어떤 지점에 도착했을 때 벽을 부수고 온 상태인지 벽을 부수지 않은 상태인지 큐에 추가로 넣어 주어야 하고, 이 상태를 추가로 방문 체크를 해야 한다. 그리고 그때의 거리 값도 큐에 추가해줘서 N, M에 도달했을 때 종료함으로 최단 거리를 찾을 수 있다.

평소에 BFS 최단거리의 방문처리는 visit[x][y] 라고 했을 때 이 문제는 visit[x][y][현재벽을부순개수] 로 처리해야 한다.

 

• BFS 사용
• Queue에 X좌표 Y좌표 거리정보 벽을 부순상태정보 추가하여 탐색
• 방문처리는 visit[x][y][현재벽을부순개수] 로 처리
• N, M 에 도달했을 때 종료 그때의 거리 값을 정답으로 출력 
• 탐색이 끝나도 N, M에 도달하지 못할 경우에는 -1 출력

---

[소스 코드]

//백준 2206 벽 부수고 이동하기
import java.io.*;
import java.util.*;

class Node{
	int x;
	int y;
	int dist;
	int boom;
	Pair(int x, int y, int dist, int boom){
		this.x = x;
		this.y = y;
		this.dist = dist;
		this.boom = boom;
	}
}

public class Node{

	static final int dx[] = {0,0,1,-1};
	static final int dy[] = {1,-1,0,0};
	static int n,m,ans;
	static boolean visit[][][];
	static int map[][];
	public static void main(String[] args) throws IOException {
		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];
		visit = new boolean[n][m][2];
		ans = -1;

		for(int i=0; i<n; i++) {
			String s = br.readLine();
			for(int j=0; j<m; j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		bfs();
		
		System.out.println(ans);
			
	}
	
	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0,0,1,0));
		visit[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			int x = now.x;
			int y = now.y;
			
			if(x==n-1 && y == m-1) {
				ans = now.dist;
				return;
			}
			
			for(int k=0; k<4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(0>nx || nx>=n || 0>ny || ny>=m) continue;
				
				if(map[nx][ny] == 0 && !visit[nx][ny][now.boom]) { //벽이 아닐경우
					visit[nx][ny][now.boom] = true;
					q.add(new Node(nx,ny,now.dist+1,now.boom));
				}else { //벽이 있는경우
					if(now.boom == 0 && !visit[nx][ny][now.boom+1]) { //벽을 부순적이 없을때
						visit[nx][ny][now.boom+1] = true;
						q.add(new Node(nx,ny,now.dist+1,now.boom+1));
					}
				}
				
			}
		}
		
	}
}

 

 

깨달음의 출처 - https://www.acmicpc.net/board/view/27386