BOJ 2206 : 벽 부수고 이동하기

알고리즘 문제 전체 링크

 

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

 

 

BOJ 2178 : 미로 탐색에서 BFS를 이용하여 길찾기 문제를 해결할 수 있었다.

벽 부수고 이동하기의 경우는 벽 1개를 부술 경우 최단 거리가 달라지기 때문에 난이도가 약간 더 높다.

 

먼저 방문 여부를 위해 visit 배열을 사용한다.

이 때, visit[0][MAX][MAX]는 벽을 0번 부순 visit 배열이고,

visit[1][MAX][MAX]는 벽을 1번 부순 visit 배열로 가정한다.

 

아래의 미로에서 (1, 1)부터 미로를 탐색한다고 가정해보자.

visit[0]의 (1, 1)은 1로 시작하게 된다.

 

보통 다음 좌표가 벽이 있는 경우, queue에 넣지 않지만,

visit[0]에서 넘어온 queue의 다음 좌표가 벽이라도 queue에 담을 수 있다.

단, queue에 담더라도, visit[1]에 check를 한다.

 

따라서 visit[0]의 2는 벽이 없기 때문에 2로 표시되었고,

visit[1]의 2는 벽을 한번 부쉈기 때문에 2가 된다. 

(실제 MAP이 1인 곳에 visit이 check된다.)

 

visit[0]의 (1, 2)도 벽을 한 번 부술 수 있기 때문에, visit[1]의 (2, 2)에 표시가 된다.

즉, visit[1]의 (2, 2)의 3은 visit[1]의 (2, 1)에서 +1이 된 것이 아니라,

visit[0]에서 벽을 부쉈기 때문에 3이 된 것이다.

 

마찬가지로 visit[1]의 (2, 3)은 visit[0]의 (1, 3)에서 벽을 부순 경우가 된다.

 

최종적으로 visit[1]에서 도착지점 (5, 4)에 도착하면 아래와 같이 visit이 만들어진다.

visit[1]의 초록색 숫자가 visit[0]에서 벽을 부순 경우와 연결된다.

 

visit[0]이든 visit[1]이든 먼저 도착한 쪽이 종료하도록 하면, 최단 거리를 알 수 있게 된다.

---

문제를 풀기 위해 QUEUE를 아래와 같이 정의한다.

보통 (r, c)를 사용하지만, k를 추가하여 현재 queue가 어떤 visit에 포함되는지 구분한다.

 

이때, queue의 memory는 MAP 보다 2배 더 필요하게 된다.

벽을 부수지 않은 MAP과 벽을 부순 MAP이 2개 존재하기 때문이다.

#define MAX (1000 + 10)

int N, M;
int MAP[MAX][MAX];
int visit[2][MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int k;
}QUEUE;

QUEUE queue[MAX * MAX * 2]; 
int rp, wp;

 

input은 아래와 같이 받는다.

보통 좌표 탐색을 위해 MAP 주변을 1로 만들었으나, 벽을 한 번 부술 수 있기 때문에 경계 조건을 이용해야 한다.

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%1d", &MAP[r][c]);
}

---

이제 미로 탐색 또는 길찾기의 BFS와 동일한 로직에서 조금만 수정하면 된다.

 

길찾기의 로직은 아래와 같다.

 - 현재의 queue의 다음 좌표 (4 방향)가 0이고, visit도 0이면 queue에 담는다.

 

벽을 한 번 부수는 경우의 로직은 아래와 같다.

 - k = 0일 때, 현재의 queue의 다음 좌표 (4 방향)가 0이고, visit[0]도 0이면 queue에 담는다.

 - k = 0일 때, 현재의 queue의 다음 좌표 (4 방향)가 1이고, visit[1]도 0이면 queue에 담는다.

 - k = 1일 때, 현재의 queue의 다음 좌표 (4 방향)이 0이고, visit[1]도 0이면 queue에 담는다.

while (wp > rp)
{
	QUEUE out = queue[rp++];

	if (out.r == N && out.c == M) return visit[out.k][out.r][out.c];

	for (int i = 0; i < 4; i++)
	{
		int nr = out.r + dr[i];
		int nc = out.c + dc[i];

		if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

		if (out.k == 0) /* k = 0일 때, */
		{
			/* queue의 다음 좌표가 0이고 visit[0]도 0 */
			if (MAP[nr][nc] == 0 && visit[0][nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].k = 0;

				visit[0][nr][nc] = visit[0][out.r][out.c] + 1;
			}		
			/* queue의 다음 좌표가 1이고 visit[1]도 0 */
			else if (MAP[nr][nc] == 1 && visit[1][nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].k = 1;

				visit[1][nr][nc] = visit[0][out.r][out.c] + 1;
			}
		}
		else /* k = 1일 때, */
		{
			/* queue의 다음 좌표가 0이고 visit[1]도 0 */
			if (MAP[nr][nc] == 0 && visit[1][nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].k = 1;

				visit[1][nr][nc] = visit[1][out.r][out.c] + 1;
			}
		}
	}
}

BFS의 종료 조건은 pop된 queue의 좌표가 (N, M)일 때가 된다.

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (1000 + 10)

int N, M;
int MAP[MAX][MAX];
int visit[2][MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int k;
}QUEUE;

QUEUE queue[MAX * MAX * 2]; 
int rp, wp;

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%1d", &MAP[r][c]);
}

void output(int map[][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int BFS(int s, int e)
{
	wp = rp = 0;

	visit[0][s][e] = 1;

	queue[wp].r = s;
	queue[wp++].c = e;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == N && out.c == M) return visit[out.k][out.r][out.c];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

			if (out.k == 0) /* k = 0일 때, */
			{
				/* queue의 다음 좌표가 0이고 visit[0]도 0 */
				if (MAP[nr][nc] == 0 && visit[0][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = 0;

					visit[0][nr][nc] = visit[0][out.r][out.c] + 1;
				}		
				/* queue의 다음 좌표가 1이고 visit[1]도 0 */
				else if (MAP[nr][nc] == 1 && visit[1][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = 1;

					visit[1][nr][nc] = visit[0][out.r][out.c] + 1;
				}
			}
			else /* k = 1일 때, */
			{
				/* queue의 다음 좌표가 0이고 visit[1]도 0 */
				if (MAP[nr][nc] == 0 && visit[1][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = 1;

					visit[1][nr][nc] = visit[1][out.r][out.c] + 1;
				}
			}
		}
	}

	return -1;
}

int main(void)
{
	input();

	printf("%d\n", BFS(1, 1));

	return 0;
}