[알고리즘] 백준 2206번 벽 부수고 이동하기 :: 우유

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

2206번: 벽 부수고 이동하기

---

BFS의 최단거리를 찾아낸다는 특성을 가지고 풀수 있는 문제지만 벽을 한번 부수고 가야하는 것을 고려해야 하기때문에 생각이 조금 필요한 문제였다.

1. 벽을 부수고 온 경우와 부수고 오지 않은 경우 각각 다른 방문배열에 저장 (3차원 배열)

2.  Class 내에 내부 클래스를 사용하여 필요한 변수를 저장

 

핵심 포인트는 벽을 부수고 가는 경우와 벽을 부수고가지 않는 경우를 모두 고려해야하는데 벽을 부수고 가지 않는 경우가 더 최단거리 일수도 있기때문에  3차원 배열을 사용하여 [0][ny][nx]에 벽을 부수지 않고 방문한 경우, [1][ny][nx]에는 벽을 부수고 방문한 경우, 모두 저장해줘야한다. 

---

​

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

	static int N, M;
	static boolean visited[][][];
	static int map[][];
	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };

	static class Point {
		int x, y, dis;
		boolean destroyed;

		public Point(int x, int y, int dis, boolean destroyed) {
			this.x = x;
			this.y = y;
			this.dis = dis;
			this.destroyed = destroyed;
		}
	}

	public static void main(String[] agrs) 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());

		visited = new boolean[2][N + 1][M + 1];
		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String temp = br.readLine();
			for (int j = 1; j <= M; j++) {
				map[i][j] = temp.charAt(j - 1) - '0';
			}
		}

		BFS();

	}

	static void BFS() {
		Queue<Point> qu = new LinkedList<Point>();

		qu.add(new Point(1, 1, 1, false));

		visited[0][1][1] = true;

		while (!qu.isEmpty()) {

			Point curP = qu.poll();

			if (curP.y == N && curP.x == M) {
				System.out.println(curP.dis);
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int ny = curP.y + dy[i];
				int nx = curP.x + dx[i];

				if (ny <= 0 || nx <= 0 || N < ny || M < nx)
					continue;

				// 벽이 아닌 경우
				if (map[ny][nx] == 0) {
					//지금까지 벽을 부순적인 없는 경우
					if (!curP.destroyed && !visited[0][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, false));
						visited[0][ny][nx] = true;
					}
					// 벽을 부수고 온경우
					else if(curP.destroyed && !visited[1][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
				// 벽인 경우
				else {
					// 벽을 부시고 방문한 적이 없으면
					if (!visited[1][ny][nx] && !curP.destroyed) {
						// 벽을 부시고 방문
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
			}

		}

		System.out.println(-1);

	}

}