[BAEKJOON_2206 - JAVA] 벽 부수고 이동하기

문제

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

풀이

• 30분을 잡고 시작했지만 3시간이 걸렸던 어려웠던 문제 보통의 BFS와 다르게 방문관리를 2가지 버전으로 해주어야 했다. ( 시작 시간 AM 01:00 ~ 종료 시간 : AM 04:00)
• 클래스 Info를 만들어 ( 행, 렬, 이동한칸의 개수, 벽을 부순 여부)를 큐에 담았지만 2차원 배열의 방문관리로는
  문제를 풀 수 없었음.
• 중요한 포인트
  벽을 부수고 먼저 도착했을 경우, 나중에 도착한 벽을 부수지 않은 경우가 방문처리 되어 제외되는 상황이 발생.
  EX)
  5번의 이동으로 (3,3)을 벽을 하나 부수고 이동했다고 가정하자.
  이후 10번의 이동으로 (3,3)에 벽을 부시지 않고 이동한 경우 (3,3)은 방문처리되어 탐색에서 제외된다.
  하지만 (3,3) 이후의 경로에서 반드시 벽을 1번 부셔야 도착을 할 수 있는 경우가 발생한다.
  이 문제를 이해하는데 시간을 많이 소요했다.
• 해결 방법
  3차원의 방문처리 배열을 만든다.
  EX)
  [row][col][0] = 벽을 부수지 않은 상태의 방문
  [row][col][1] = 벽을 부순 상태의 방문
  벽을 부순 Info들은  [row][col][1]을 통해 방문 관리를 한다. (벽을 부순 여부는 Info 클래스에 담았다.)
• 마지막에 N=1,M=1 인 상황의 예외처리를 잡을 수 있었다.
• 특정 상황이 주어진 최소경로의 경우에는 참고할 수 있었으며, 예외는 최소단위를 먼저 확인해보자.

 

 

과정

1. 정보를 들고 다닐 Info 클래스를 작성
2. BFS( 행, 렬, 이동한 칸의 개수, 벽을 부순 여부) / (문제에서 제시한 조건, 이동한 칸의 개수는 시작과 도착을 포함.)
3. 첫 배열의 방문처리
4. 사방탐색 && 도착한 경우(N과 M을 확인하는 과정)
5. 범위 검사
6. 벽을 부순 상태 체크와 이에 따른 if-else문 통과
7. 벽을 부수지 않은 경우 이에 따른 if-else문 통과 ( 이동가능한 경우와 벽을 부셔야 하는 경우)
8. 방문 처리
9. 문제의 조건에서 제시한 길이 없는 경우 -1 출력 이외에 return받은 값을 출력(삼항연산자 활용)
10. 예외처리 N과M에 입력받는 값이 1인 경우 -> 1 출력 ( 예외상황은 최소단위부터 꼼꼼히 체크하자)

 

 

알고리즘 지식

• BFS ( 3차원 방문관리)

 

 

JAVA코드

package BFS_DFS;

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

class Info {
	int row;
	int col;
	int move;
	boolean wall;

	public Info(int row, int col, int move, boolean wall) {
		super();
		this.row = row;
		this.col = col;
		this.move = move;
		this.wall = wall;
	}

}

public class BJ_2206_벽부수고이동하기 {

	static int[][] map;
	static boolean[][][] visited;
	static int N, M;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	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());
		int ret = 0;
		if (N == 1 && M == 1) {
			System.out.println(1);
		} else {
			map = new int[N + 1][M + 1]; // Map
			visited = new boolean[N + 1][M + 1][2]; // 방문 관리 ( 0 : 부수지 않은 경우 따로 관리 & 1 : 벽을 부순 경우 )
			for (int i = 1; i <= N; i++) {
				String str = br.readLine();
				for (int j = 0; j < M; j++) {
					map[i][j + 1] = str.charAt(j) - '0';
				}
			}
			// ========================== end of input ==========================

			ret = BFS(new Info(1, 1, 1, false)); // 시작지점, 이동한 칸의 개수, 벽을 부신 여부
			System.out.println(ret != 0 ? ret : -1);
		}
	} // end of main

	// 범위 체크
	private static boolean isValid(int row, int col) {
		if (row < 1 || row > N || col < 1 || col > M) {
			return false;
		}
		return true;
	}

	private static int BFS(Info info) {
		Queue<Info> q = new LinkedList<Info>();
		q.offer(info); // 출발지를 큐에 추가
		visited[info.row][info.col][0] = true; // 방문 체크
		while (!q.isEmpty()) {
			int row = q.peek().row; // 행
			int col = q.peek().col; // 열
			int move = q.peek().move; // 이동한 칸의 개수
			boolean wall = q.poll().wall; // 벽을 부순 여부

			// 사방 탐색
			for (int k = 0; k < 4; k++) {
				int next_row = row + dy[k];
				int next_col = col + dx[k];

				// 도착한 경우
				if (N == next_row && M == next_col) {
					return move + 1;
				}

				// 범위 검사
				if (isValid(next_row, next_col)) {
					int next_way = map[next_row][next_col]; // 다음칸의 상태

					// 벽을 부수지 않은 경우
					if (wall == false) {
						if (next_way == 0) { // 이동할 칸이 벽이 아닌 경우
							if (visited[next_row][next_col][0] == false) {
								q.offer(new Info(next_row, next_col, move + 1, wall));
								visited[next_row][next_col][0] = true; // 이동한 칸으로 방문 관리
							}
						} else { // 이동할 칸이 벽인 경우
							if (visited[next_row][next_col][0] == false) {
								q.offer(new Info(next_row, next_col, move + 1, true));
								visited[next_row][next_col][0] = true; // 이동한 칸으로 방문 관리
							}
						}
					}
					// 벽을 부순 경우
					else {
						if (next_way == 0) { // 이동이 가능한 경우 ( 벽을 부셨으므로 더이상 벽은 검사하지 않는다.)
							if (visited[next_row][next_col][1] == false) { // 벽을 부수고 방문한적이 없는 경우
								q.offer(new Info(next_row, next_col, move + 1, wall));
								visited[next_row][next_col][1] = true; // 이동한 칸으로 방문 관리
							}
						}
					}

				} // end of isValid
			}
		}
		return 0;
	}
}