[Java] 백준 2206번 : 벽 부수고 이동하기

1. 문제

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

 

2. 풀이과정

최단거리 구하기는 보통 bfs, 도착지점까지 경로를 구한다면 dfs를 주로 사용하는 것 같다.

이 문제는 최단거리를 구하는 문제로 bfs를 사용하여 풀었다. 최단거리만큼만 모든 경로를 탐색하기 때문에 최악의 경우(모든 경로 끝까지 전체탐색)을 막을 수 있다.

 

처음에는 boolean visited[N][M][2]로 3차원배열을 사용해서 visited[N][M][0]에는 벽을 안 뚫고 갈 때 check, visited[N][M][1]에는 벽을 뚫고 갈 때를 check해서 벌써 방문했다면, 넘어가도록 했다. 하지만 tip에 적어놓은 것처럼 벽을 안 뚫고 간 곳을 벽을 뚫고 와서 다시 방문하는 건 낭비이다.

 

tip) 벽을 안 뚫고 방문했던 곳을 벽을 뚫고 와서 다시 방문할 필요가 없다. 벽을 안 뚫고 갈 때가 무조건 같거나 더 빠르기 때문이다.

반대로 벽을 뚫고 와서 방문한 곳은 벽을 안 뚫고 또 온 경우 방문할 필요가 있다. 나중에 벽을 뚫고 갔을 때 더 빨리 도착할 수 있기 때문이다.

 

이를 코드에 적용한 방법은 방문 배열을 int로 두고 모든 값을 2로 초기화해주었다.

벽을 안 뚫고 갔을 때가 0, 벽을 뚫고 갔을 때가 1로 queue에 들어가기 때문에

 

* visited는

1) 2 = 아직 방문 안 함

2) 1 = 벽을 뚫고 와서 or 지금 뚫고 방문함.

3) 0 = 벽을 안 뚫고 와서 방문함.

으로 표기된다.

 

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 N, M;
	static int[][] map;
	static int[][] visited;
	
	public static int bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {x, y, 0});//좌표, 부순 벽 개수
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		
		int[] node;
		int d = 0, result=-1;
		outloop : while(!q.isEmpty()) {
			d++;
			for(int j=0, size = q.size();j<size;j++) {
				node = q.poll();
				if(node[0]==N-1 && node[1]==M-1) {
					result = d;
					break outloop;
				}
				for(int i=0;i<4;i++) {
					int nx = node[0] + dx[i];
					int ny = node[1] + dy[i];
					//벽을 안 뚫고 먼저 방문했다면 pass, 한번도 방문안했으면 무조건 들어감
					if(0<=nx && nx<N && 0<=ny && ny<M && visited[nx][ny] > node[2]) {
						if(map[nx][ny]==0) {
							visited[nx][ny] = node[2];
							q.offer(new int[] {nx, ny, node[2]});
						}
						else if(map[nx][ny]==1 && node[2]==0){//벽인데, 아직 안 뚫고 갔다면
							visited[nx][ny] = 1;
							q.offer(new int[] {nx, ny, 1});
						}
					}
				}
			}
			
		}
		return result;
	}

	public static void main(String[] args) throws Exception {
		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];
		visited = new int[N][M];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				map[i][j] = br.read()-'0';
				visited[i][j] = 2;
			}
			br.readLine();
		}
		System.out.println(bfs(0, 0));
	}
}