[알고리즘/문제풀이][BOJ 2206번] 벽 부수고 이동하기

벽 부수고 이동하기는 변형된 BFS 문제입니다. BFS를 기반으로 문제를 풀어야 하지만 벽을 1회 부술 수 있다는 사실 때문에 단순 BFS에서 조금의 변형이 필요합니다.

BFS는 이동할 수 있는 노드를 탐색하면서 중복된 탐색을 방지하기 위해 방문 여부를 표시하는 자료구조를 사용합니다. 한 노드에서 다른 노드로 가는 이동 조건이 모두 동일하다면 하나의 자료구조에 방문 여부를 표시하면 충분합니다. 하지만 이동 조건이 달라진다면 하나의 자료구조에서만 방문 여부를 표시하는 것을 문제를 해결할 수 있음을 보장하지 못합니다. 이동조건이 다르기 때문에 같은 노드를 뒤늦게 방문하여도 최단거리의 경로가 될 수도 있습니다. 따라서 하나의 자료구조에 대한 중복 조건 체크는 의미가 없으며 이동 조건의 수에 따라 방문 여부를 표시할 자료구조를 별도로 마련해야 합니다.

 이 문제의 경우, 벽을 뚫지 않은 상태에서 발견한 노드에서는 다음 노드로 가기 위해 벽을 뚫고 이동할 수 있고 벽을 뚫지 않고 이동할 수도 있습니다. 반면 이미 벽을 뚫고 발견한 노드에서는 벽을 뚫지 않으면서 발견한 노드로만 이동할 수 있습니다. 

문제에서 두 가지의 이동 조건이 존재하므로 큐는 공유하되 각각의 상태에 대해 별도의 방문 표시 자료구조를 만들어야 합니다. 큐는 노드를 시간 순으로 탐색하도록 도와주는 자료 구조에 불과하기 때문에 서로 다른 이동조건 간 간섭을 일으키지 않습니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com

int N, M;
int map[1020][1020];
int visit[2][1020][1020];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int min = 123456789;

struct que {
	int x, y, time, wall;
};

int wp, rp;

struct que queue[1020 * 1020 * 4];

void enqueue(int x, int y, int time, int wall) {
	queue[wp].x = x;
	queue[wp].y = y;
	queue[wp].time = time;
	queue[wp].wall = wall;
	wp++;
	return;
}

int empty() {
	return wp == rp;
}

struct que dequeue() {
	return queue[rp++];
}

void BFS() {

	visit[0][0][0] = 1;
	enqueue(0, 0, 1, 0);

	while (!empty()) {
		struct que temp = dequeue();
		if (temp.x == M - 1 && temp.y == N - 1) {
			printf("%d\n", temp.time);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = temp.x + dx[i];
			int ny = temp.y + dy[i];
			if (nx<0 || nx>=M) continue;
			if (ny < 0 || ny >= N) continue;

			if (temp.wall == 1) {
				if (map[ny][nx] == 1) continue;
				if (visit[1][ny][nx] == 1) continue;
				

				visit[1][ny][nx] = 1;
				enqueue(nx, ny, temp.time + 1, 1);
			}
			else {
				if (map[ny][nx] == 1 && visit[1][ny][nx]==0) {
					visit[1][ny][nx] = 1;
					enqueue(nx, ny, temp.time + 1, 1);
				}
				else if(map[ny][nx]==0){
					if (visit[0][ny][nx] == 1) continue;
					visit[0][ny][nx] = 1;
					enqueue(nx, ny, temp.time + 1, 0);
				}
			}
		}
	}
	printf("%d\n", -1);
	return;
}

int main(void) {
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	BFS();
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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