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

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

2206번: 벽 부수고 이동하기

🎈 문제

 

- NxM의 행렬로 나타내는 지도에서 (1,1)에서 (N,M)으로 최단 거리로 이동하는 문제

- 0은 빈 칸, 1은 벽

- 단, 벽은 한 번 부수고 지나갈 수 있다

 

 

🎈 문제 풀이

 

- 벽을 부순다는 조건이 없으면 일반적인 미로 탐색 문제이다.

- 어떤 칸에 방문했을 때, 벽을 부순 적이 있는 경우와 아직 부순 적이 없는 경우는 다른 경우이기 때문에

- 상태(r,c) 대신에 (r, c, wall) (wall == 0이면 벽을 부순 적이 없음, 1이면 있음)으로 BFS 탐색을 진행한다.

 

- 큐(Queue)에서 하나씩 빼가기

- 다음칸이 빈칸인 경우, 벽을 부순 것과 상관없이 항상 이동할 수 있다. => 다음칸이 방문한 적이 없으면 무조건 방문

- 다음칸이 벽인 경우, 방금 꺼낸 큐의 wall이 벽을 부순 횟수가 없어야 한다. 

   - 다음 칸이 벽이면  wall+1

 

🎈 고려사항

 

1. 현재정점 기준, 벽을 한번도 부수지 않고 이동하는 경우, 벽을 한번 부수고 이동하는 경로를 따로 체크

 

2. 2차원 배열 distance가 아닌 3차원 배열 distance[row][col][2]을 선언

• distance[r][c][0] = 벽을 부수지 않고 이동하는 경우 최단 거리 => 0과 1은 Map 클래스의 k 멤버변수에서 가져옴
• distance[r][c][1] = 벽을 부수고 이동하는 경우 최단 거리

3. Map 클래스의  k 멤버변수가 벽을 부수고 온 경우인지 아닌지 판별

 

4. 이전에 벽을 부수지 않은 경우(k==0) 

• 다음칸이 빈칸인 경우(=0) : 그대로 방문처리
• 다음칸이 빈칸인 경우
  • 해당 벽을 부수고 이동(k를 1로 바꿈)

5. 이전에 벽을 부순 경우(k==1)

• 벽을 만났을 경우
  • 이미 벽을 한번 부쉈으므로 해당 벽을 부술 수 없기에  탐색 지점에서 종료
• 벽을 만나지 않았을 경우
  • 그대로 방문처리해주고 탐색 계속

 

빈칸(이전에 벽 부수기 x)	빈칸
	벽
빈칸(이번에 벽 부쉈음)	빈칸

 

🎈 소스코드

 

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

public class Q2206 {
	static int N, M;
	static int[][] moves = {{+1, 0},{-1,0}, {0,+1}, {0, -1}};
	static int[][][] visited;

	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()); // r
		M = Integer.parseInt(st.nextToken()); // c
		char[][] arr = new char[N][M];
		visited = new int[N][M][2];

		for(int i=0; i<N; i++) {
			arr[i] = br.readLine().toCharArray();
		}

		System.out.println(bfs(arr));
	}

	static int bfs(char[][] arr) {
		Queue<Map> queue = new LinkedList<>();

		queue.add(new Map(0,0,0));
		visited[0][0][0] = 1;
		while (!queue.isEmpty()) {
			Map map = queue.remove();
			int r = map.r, c = map.c, k = map.k;
			for(int[] move : moves) {
				int rx = r+move[0];
				int ry = c+move[1];
				if(rx < 0 || rx >=N || ry < 0 || ry >=M) continue;

				// 다음 칸이 빈칸인 경우, 벽을 부순것과 상관없이 항상 이동할 수 있다.
				// 즉, Map의 k 멤버변수가 0,1 상관없으면서 방문한 적이 없어야 한다(=0)
				if(arr[rx][ry] == '0' && visited[rx][ry][k] == 0) {
					visited[rx][ry][k] = visited[r][c][k]+1;
					queue.add(new Map(rx,ry,k));
				}

				// 다음 칸이 벽인 경우, 이전에 벽을 부순 적이 없어야 함
				if(k==0 && arr[rx][ry] == '1' && visited[rx][ry][k+1] == 0) {
					visited[rx][ry][k+1] = visited[r][c][k]+1;
					queue.add(new Map(rx, ry, k+1));
				}
			}
		}

		// 한개의 벽을 부수고 최단 경로, 벽을 부수지 않고 최단 경로 비교
		if(visited[N-1][M-1][0] != 0 && visited[N-1][M-1][1] != 0) {
			return Math.min(visited[N-1][M-1][0], visited[N-1][M-1][1]);
		} else if(visited[N-1][M-1][0] != 0) {
			return visited[N-1][M-1][0];
		} else if(visited[N-1][M-1][1] != 0) {
			return visited[N-1][M-1][1];
		} else {
			return -1;
		}

	}

	static class Map {
		int r;
		int c;
		int k;

		public Map(int r, int c, int k) {
			this.r = r;
			this.c = c;
			this.k = k; // 벽을 부수고 온 경우인지 아닌지 판별
		}
	}
}