[BOJ]2206번: 벽 부수고 이동하기 (c++)

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

2206번: 벽 부수고 이동하기

 

bfs. map[x][y]에 도착했을 때의 상태값 저장

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

struct info {
	pos p;
	int left; // left 만큼 벽을 부술 수 있다
	int dist; // 이동횟수
};

int N, M;
int dr_x[] = {0, 1, 0, -1};
int dr_y[] = {1, 0, -1, 0};
const int MAX = 1000;
int visit[MAX][MAX];

int bfs(vector<string>& map)
{
	// visit : 여분의 부술 벽 개수를 저장할 배열
	// -1값으로 초기화
	memset(visit, -1, sizeof(visit));

	// map[0][0]부터, 부술수 있는 벽 1개, 이동횟수 1로 시작
	queue<info> q;
	q.push({0, 0, 1, 1});
	
	// map[0][0]에 도착했을 때 부술 수 있는 벽 개수 1개
	visit[0][0] = 1;

	while (!q.empty())
	{
		pos p = q.front().p;
		int left = q.front().left;
		int dist = q.front().dist;
		q.pop();

		// map[N - 1][M - 1]에 도착하면 이동횟수 반환
		if (p.x == N - 1 && p.y == M - 1)
		{
			return dist;
		}

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			// 범위를 벗어나면 continue
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
			{
				continue;
			}

			/*
				다음위치가 빈칸이고, 
				여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면
			*/
			if (map[nx][ny] == '0' && visit[nx][ny] < left)
			{
				// visit[nx][ny]에 현재 여분 벽 개수 저장
				visit[nx][ny] = left;
				
				// 이동횟수 + 1 하고 현재 정보를 큐에 push
				q.push({ nx, ny, left, dist + 1 });
			}
			/*
				부술 수 있는 벽 개수가 남아있고, 다음위치가 벽이고, 
				여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면
			*/
			else if (left > 0 && map[nx][ny] == '1' && visit[nx][ny] < left - 1)
			{
				// visit[nx][ny]에 부수고 난 후 여분 벽 개수 저장
				visit[nx][ny] = left - 1;

				// 이동횟수 + 1 하고 현재 정보를 큐에 push
				q.push({ nx, ny, left - 1, dist + 1 });
			}
		}
	}

	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> M;
	vector<string> map(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	// map[0][0] ~ map[N - 1][M - 1] 최단 거리 출력
	cout << bfs(map);

	return 0;
}

 

처음에 연구소 문제와 비슷하게 생각했지만, 전혀 다른 문제였다. 

 

TIP1

당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다.

우선 최단 경로로 이동해야한다는 문제 요구사항에서 bfs풀이가 적합함을 알 수 있다.

 

 

 

TIP2

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면,
벽을 한 개 까지 부수고 이동하여도 된다.

 

이 부분이 골치가 아파지는 지점이다.

이런저런 아이디어를 내보자. 부술 수 있는 벽 개수를 짧게 left라고 하겠다.

 

 

1. 빈 칸에다가 벽 1개를 새로 세우는 경우를 모두 구하고

각각의 경우에서 strt ~ end까지 가는 최단 경로를 구할까?

--> 시간초과. 매우 비효율적이다.

 

2. 큐에 {위치값, left} 를 저장해서

left값이 남아있으면 {위치값, left - 1}을 push할까?

--> 틀렸다! 

 

3. [x][y]에 도착했을 때의 left값을 저장하는 배열을 따로 만들까?

--> YES

 

 

 

ㅜㅜ 수많은 실패의 흔적...

2번은 틀리고, 3번은 맞는 이유를 그림으로 설명하겠다.

다음과 같은 예시가 주어진다고 하자. 

S ~ E까지 반드시 1번 벽을 부수어야 한다

 

 

S ~ E까지 가는 경로 2가지를 비교해보면,

 

오른쪽처럼 map[0][4]전에 벽을 부수지 않아야지만 목표지점까지 갈 수 있다.

 

남은 벽 개수를 메모이제이션 해야하는 이유가 바로 map[0][4]이다.

같은 지점에 도착할 때, 벽을 깨고 온 경로보다 벽을 깨지 않고 온 경로가 더 늦게 도착하게 된다.

이때 무조건 이동횟수 기준으로만 큐에 push하게 되면, 위의 왼쪽 그림처럼 실패하게 된다. 

 

 

따라서 기존에 visit[x][y]에 저장된 left 값 < 현재 left값 이라면

큐에 push해서 목표지점에 갈 수 있는지 확인해주어야 한다. 

위의 아이디어에서 2번은 left값을 기준으로 비교하지 않았기 때문에 틀렸다.

/*
	다음위치가 빈칸이고, 
	여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면
*/
if (map[nx][ny] == '0' && visit[nx][ny] < left)
{
	visit[nx][ny] = left;
	q.push({ nx, ny, left, dist + 1 });
}
/*
	부술 수 있는 벽 개수가 남아있고, 다음위치가 벽이고, 
	여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면
*/
else if (left > 0 && map[nx][ny] == '1' && visit[nx][ny] < left - 1)
{
	visit[nx][ny] = left - 1;
	q.push({ nx, ny, left - 1, dist + 1 });
}

 

 

 

 

TIP3

visit[left][x][y]와 같이 3차원 배열을 만드는 것은 안될까?

 

--> 된다. 그 경우에는 아래와 같이 구현할 수 있다. 사실 더 직관적이다.

const int MAX = 1000;
int dist[2][MAX][MAX];

...

int bfs(vector<vector<int>>& map)
{
	...

	if (p.x == N - 1 && p.y == M - 1)
	{
		return dist[left][p.x][p.y];
	}

	for (int i = 0; i < 4; ++i)
	{
	...

		if (dist[left][nx][ny] == 0)
		{
			if (map[nx][ny] == 0)
			{
				dist[left][nx][ny] = dist[left][p.x][p.y] + 1;
				q.push({ nx, ny, left });
			}
			else if (left > 0)
			{
				dist[left - 1][nx][ny] = dist[left][p.x][p.y] + 1;
				q.push({ nx, ny, left - 1 });
			}
		}
	...
}

 

 

그런데 왜 저렇게 안했는가... 하면,

만약 부숴야할 벽 개수가 많아질 경우

공간 효율이 쓸데없이 매우 낮아질 것을 염려했기 때문이다.

visit[left][x][y] 는 left가 늘어날 수록 몇배로 커지니까!

 

 

끝!