[JAVA] 백준 2206 벽 부수고 이동하기 [BFS]

전체 코드

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 baek {

	static int N, M, MIN = Integer.MAX_VALUE;
	static char arr[][];
	static boolean chk = false;
	static int dy[] = { 1, -1, 0, 0 };
	static int dx[] = { 0, 0, 1, -1 };

	static boolean v[][][];
//	static boolean v[][];
	
	static class Point {
		int y;
		int x;
		int dis;
		int wall;
		
		Point(int y, int x, int dis, int wall) {
			this.y = y;
			this.x = x;
			this.dis = dis;
			this.wall = wall;
		}
	}

	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());

		arr = new char[N][M];
		v = new boolean[N][M][2]; // 3차원 방문 배열, 벽을 마주친 경우와 마주치지 않은 경우
//		v = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char[] tmp = st.nextToken().toCharArray();
			for (int j = 0; j < M; j++) {
				arr[i] = tmp;
			}
		}

		bfs();
		
//		v[0][0] = true;
//		dfs(0, 0, 1);
		
		if(MIN == Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(MIN);

	}
	
	private static void bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0, 0, 1, 0));
		v[0][0][0] = true;
		v[0][0][1] = true;
//		v[0][0] = true;
		
		while (!q.isEmpty()) {
			Point p = q.poll();
			if(p.y == N-1 && p.x == M-1) {
				if(MIN > p.dis)
					MIN = p.dis;
				
				continue;
			}
//			System.out.println(p.y + " " + p.x);
			
			for (int i = 0; i < 4; i++) {
				int ry = p.y + dy[i];
				int rx = p.x + dx[i];
				
				if (ry >= 0 && ry < N && rx >= 0 && rx < M) {
					if(arr[ry][rx] == '1') { // 벽인경우
						if(p.wall == 0 && !v[ry][rx][1]) { // 벽을 마주친적이 있는지 여부와 해당 벽에 방문한 적이 있는지 체크
							v[ry][rx][1] = true; // 벽을 마주치지 않았고 다른 케이스가 해당 벽을 지나간적이 없다면
							q.add(new Point(ry, rx, p.dis+1, p.wall+1));
						}
					}else { // 벽이 아닌경우
						if(!v[ry][rx][p.wall]) { // p.wall에 따라 현재 벽을 마주친적이 있는 경우와 마주친 적이 없는 두가지 경우로 나뉘어 진행된다.
							q.add(new Point(ry, rx, p.dis+1, p.wall));
							v[ry][rx][p.wall]= true; 
						}
					}
//					if (ry >= 0 && ry < N && rx >= 0 && rx < M && !v[ry][rx]) {
//					if(arr[ry][rx] == '0') { // 0만 허용
//						q.add(new Point(ry, rx, p.dis+1, p.wall));
//						v[ry][rx] = true;
//					}else if(p.wall == 0 && arr[ry][rx] == '1') {
//						q.add(new Point(ry, rx, p.dis+1, p.wall+1));
//						v[ry][rx] = true;
//					}
//					
				}
			}
		}
	}

}

 

주석 처리된 부분은 첫 풀이이다. 테스트 케이스는 맞았지만 채점을 누르면 틀렸다고 나왔고 검색과 반례를 이용해 다시 푼결과이다.

 

처음엔 부순 벽의 개수만을 세어 이동하며 체크 했지만 하나의 반례가 존재한다.

7 4 
0000 
1110 
0000 
0111 
0000 
0011 
0010

 

이 경우 도착지가 1로 갇혀있는 경우인데, 주석처리된 코드로 돌리면 벽을 부수기 전에 이미 모든 visit 배열이 true 처리되어있어 끝에 다다르면 그대로 끝나 -1이 출력된다.

 

하지만 정답이 나온 코드는 3차원 배열을 이용해 벽을 마주친 적이 없는 상태로 방문하는 경우와 벽울 마주친 후 방문하는 경우로 나뉘어 탐색하기 때문에 벽을 마주친 상태에서 도착지 근처에 왔다면, 다시 돌아가 벽을 마주친 적이 없는 경우로 도착지 근처에 온 후 마지막 벽을 부수고 도착지에 도달할 수 있다.

 

설명이 길지만 poll되는 y와 x를 출력하며 보면 더 직관적으로 깨달을 수 있다.