[알고리즘] 벽 부수고 이동하기 (백준 2206번)

2206번: 벽 부수고 이동하기

 지도의 끝까지 이동할 때의 최단 경로를 구하는 BFS 문제이다. 다만 벽을 1개까지 부수고 이동할 수 있다는 조건이 있다. 

 만약에 브루트 포스로 구한다고 가정해보자. 모든 경우의 수를 따지려면 맵의 벽의 개수 만큼 BFS를 돌려야 하는데 한 번 BFS를 돌릴 때 최악의 연산 횟수가 3백만번 정도된다. (O(V+E) = 1000 * 1000 + 1000 * 999 + 1000 * 999)

 거기에 벽의 개수 최악의 경우 NM개를 곱하게 되면 3백만번 * 1백만번이되므로 무조건 시간초과가 발생한다. 때문에  한 번의 탐색으로 답을 찾아내야한다.

 

Solution

 BFS에서 노드의 방문 여부를 판단하는 visited 배열은 일어날 수 있는 경우의 수를 의미하기도 한다. 여기에서 각 노드는 2가지의 방문 경우의 수가 생긴다.

1. 벽을 부수고 온 경로가 방문한 경우
2. 아직 벽을 안 부수고 온 경로가 방문한 경우

 만약 경우를 2가지로 나누지 않는다면 발생할 상황에 대한 예를 들어 보겠다.

0(출발지)	0(2번 경로)	1	1
0(1번 경로)	1(2번 경로, 벽 부숨)	1	1
0(1번 경로)	0(2번 경로)	1	1
0(1번 경로)	0	1(부숴야 하는 벽)	0(도착지)

 이러한 맵이 있다고 가정했을 때, 벽을 부수지 않고 오는 1번 경로와 벽을 부수고 오는 2번 경로 2가지가 생긴다.

 이 때 두 경로는 반드시 보라색 노드를 지나쳐야 하는데 반복문의 순서상 2번 경로가 먼저 방문했다고 치자. 2번 경로는 보라색 노드를 지나더라도 뒤에 있는 벽 때문에 어차피 지나갈 수가 없다. 1번 경로는 벽을 한 번도 안 부쉈기 때문에 벽을 부수고 통과할 수 있지만 이미 보라색 노드를 2번 경로가 지나갔기 때문에 지나갈 수가 없게 된다.

 

 이런 오류가 발생하기 때문에 경우를 2가지로 나눠야 하는 것이다. 그리고 현재 위치, 이 때까지의 거리, 벽을 파괴했는지 여부를 포함하는 객체 클래스를 만들고 queue에 넣어서 사용하면 된다.

 

import javafx.geometry.Pos;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer strtok = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(strtok.nextToken());
		int M = Integer.parseInt(strtok.nextToken());

		int[][] map = new int[N+1][M+1];

		int x[] = {-1, 1, 0, 0};
		int y[] = {0, 0, -1, 1};

		for(int i = 1;i <= N;i++)
		{
			String row = br.readLine();

			for(int j = 1;j <= M;j++)
			{
				map[i][j] = row.charAt(j-1)-'0';
			}
		}



		int distance = bfs(map, N, M);

		bw.write(distance+"");
		bw.close();
	}

	static int bfs(int[][] map, int N,int M)
	{
		boolean visited[][][] = new boolean[N+1][M+1][2];

		Queue<Position> queue = new LinkedList<>();
		queue.offer(new Position(1, 1, 1, false));
		visited[1][1][0] = true;
		visited[1][1][1] = true;

		int result = Integer.MAX_VALUE;

		while(!queue.isEmpty())
		{
			Position now = queue.poll();

			if(now.x == N && now.y == M)
			{
				result = Math.min(result, now.distance);
			}

			int x[] = {-1, 1, 0, 0};
			int y[] = {0, 0, -1, 1};

			for(int i = 0;i < x.length;i++)
			{
				int next_x = now.x + x[i];
				int next_y = now.y + y[i];

				if(0 < next_x && next_x <= N && 0 < next_y && next_y <= M)
				{
					//안 깬놈
					if(!now.destory)
					{
						if(!visited[next_x][next_y][0])
						{
							visited[next_x][next_y][0] = true;

							if(map[next_x][next_y] == 0)
								queue.offer(new Position(next_x, next_y, now.distance+1, now.destory));
							else
								queue.offer(new Position(next_x, next_y, now.distance+1, true));
						}
					}
					//벽 깨고 온 놈
					else
					{
						if(!visited[next_x][next_y][1])
						{
							visited[next_x][next_y][1] = true;

							if(map[next_x][next_y] == 0)
								queue.offer(new Position(next_x, next_y, now.distance+1, now.destory));
						}
					}
				}
			}
		}

		if(result == Integer.MAX_VALUE)
			return -1;
		return result;
	}


	static class Position{

		int x, y, distance;
		boolean destory = false;

		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public Position(int x, int y, int distance, boolean destory) {
			this.x = x;
			this.y = y;
			this.distance = distance;
			this.destory = destory;
		}

		@Override
		public boolean equals(Object obj) {
			Position pos = (Position)obj;

			if(x == pos.x && y == pos.y)
				return true;
			return false;
		}
	}


	public static void main(String[] args) {
		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}