[백준] 2206번 벽 부수고 이동하기 자바

문제 (BFS, 골드4)

 

2206번: 벽 부수고 이동하기

 

 

문제 풀이

 

나에겐 이해하기 너무 어려운 문제였다...

일단 이 문제에서 궁금했던 세 가지는

 

1. 격자 최단경로에서 BFS를 쓰는 이유?

  : 트리의 경우, DFS로 두 정점 간의 거리를 구할 수 있다. BUT, 트리(거리가 하나 존재)라는 확증이 필요하다.

    그래프의 경우, 내가 구한 경로가 최단경로인지 확신할 수 없다. 

    그래프를 DFS탐색할 경우 한 정점에 대해 타고타고 내려간 경로가 최소인지 확인이 필요하다. 따라서 모든 경우에 한해 검사하여 최소를 구해야 한다. BFS는 최소의 간선을 선택해서 탐색할 수 있다. (근데 이것도 가중치 있을 경우...)

 

이 문제의 경우도 DFS로 일일이 확인하는 것보다 거리와 벽을 부쉈는지 여부를 같이 가져가면서 바로 최단거리를 구하는 것이 더 효율적인가 보다... 모르겠다. 다른 사람들이 다 BFS로 풀었다...

 

2. BFS로 먼저 마지막에 도착하는 것이 꼭 최단인 이유?

   : 해당 좌표의 주변 지점부터 큐에 넣어서 주변이 끝나고 다음 좌표로 넘어가기 때문에 자연스럽게 먼저 마지막 행렬에 도착하는 시점이 최단 경로일 수 밖에 없다..

 

3. 반복문 돌다가 벽을 안 부순 경우에서 부순 경우로 넘어갈 때, 부순 경우의 배열에 합쳐져도 되는 이유?

  : 맨 좌측 상단부터 시작하니까 →↓방향으로 내려가기 시작하는데, 만약에 위쪽이나 왼쪽으로 돌아오는 경우에는 아래로 내려가지 못하니까 이미 공사를 했을 경우고 공사없이 진행하는 경우는 아래쪽으로 무리없이 잘 내려왔을 경우니까 부수지 않은 경우가 부술 경우로 바로 합쳐지는 것 같다..!

 

 

✔️알고리즘

우선 BFS알고리즘 사용할 때 보통 방문 표시하기 위한 2차원 배열을 쓰는데, 여기서는 벽을 부순경우와 벽을 부수지 않은 경우 두 가지를 따로 방문 표시해주기 위하여 3차원 배열을 사용했다. (아니면 int형 2차원 배열 써서 각각을 숫자로 표시해줘도 가능하다)

 

두 가지 기준으로 나누는 이유는 만약 오른쪽으로 이동할 때는 벽이 있어서 부쉈지만 아래쪽으로 이동할 때는 벽이 없어서 부수지 않고 지나갈 수 있다. 그치만 앞서 오른쪽에서 벽을 부쉈다고 아래로 이동하면서 새롭게 나온 벽을 부수지 못할 이유는 없다. 그렇기 때문에 방문 배열을 두 가지 버전으로 사용해야 한다.

 

visited[r][c][0] -> 벽을 안 부순 경우

visited[r][c][1] -> 벽을 부순 경우

 

1) 벽이 아닐 경우 (map == 0)

  1-1) 벽 부순적 없고 방문 안했음

        - 큐에 값 담고 visited[0]에 true 표시

 

  1-2) 벽 부쉈고 방문 안했음

        - 큐에 값 담고 visited[1]에 true 표시

 

2) 벽일 경우 (map == 1)

   2-1) 벽 부순적 없음

      - 큐에 값 담고 visited[1]에 true표시

 

 

EX) 오른쪽으로 부수고 가는 경우와 아래쪽으로 부수지 않고 가는 경우 예시

 

- BFS로 빨간색 부분처럼 나아가면서 탐색

map배열: 대각선 방향으로 값 갱신

 

- 파란색이 벽을 부수게 되는 순간 벽을 부순 배열인 visited[][][1]로 넘어가서 방문 표시, 그리고 큐에 부순 값으로 넣기

탐색 방향에 따른 dist값

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

//벽 부수고 이동하기
public class b_2206 {
	
	static int[] dx = {-1, 1, 0, 0};	//상하좌우
	static int[] dy = {0, 0, -1, 1};
	static int N, M;
	static int[][] map;
	static boolean[][][] visited;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		map = new int[N][M];
		visited = new boolean[N][M][2];
		
		//입력 받기
		for(int i = 0; i < N; i++) {
			str = br.readLine().split("");
			for(int j = 0; j < M; j++)
				map[i][j] = Integer.parseInt(str[j]);
		}
		
		System.out.println(bfs());
		br.close();
	}
	
	//visited[0]: 벽안뚫었음, visited[1]: 벽뚫었음
	public static int bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0, 0, 1, false));
		visited[0][0][0] = true; 
		
		/*		큐 반복문 시작		*/
		while(!q.isEmpty()) {
			Point now = q.poll();
			
			if(now.x == N-1 && now.y == M-1)
				return now.dist;
			
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				int nd = now.dist + 1;
				
				if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
					//벽이 아닌 경우
					if(map[nx][ny] == 0) {
						if(now.wall == false && visited[nx][ny][0] == false) {
							q.add(new Point(nx, ny, nd, false));
							visited[nx][ny][0] = true;
						}
						if(now.wall == true && visited[nx][ny][1] == false) {
							q.add(new Point(nx, ny, nd, true));
							visited[nx][ny][1] = true;
						}
					}
					//벽인 경우
					else {
						if(now.wall == false) {
							q.add(new Point(nx, ny, nd, true));
							visited[nx][ny][1] = true;
						}
					}
				}
			}
		}
		/*		큐 반복문 끝		*/
		return -1;
	}
	
	static class Point{
		int x, y, dist;
		boolean wall;		//벽뚫음-true, 벽안뚫음-false
		
		public Point(int x, int y, int dist, boolean wall) {
			this.x = x;
			this.y = y;
			this.dist = dist;
			this.wall = wall;
		}
	}

}