백준 2206 - 벽 부수고 이동하기

문제링크

• 백준 2206

문제설명

• N x N 크기의 맵이 주어진다.
• 맵에서 0은 빈 칸, 1은 벽을 나타낸다.
• (1,1) 에서 (N,M) 까지 이동하려고 할때, 최단 경로를 구하라.
  • 만약, 벽을 부수고 이동하는 것이 더 경로가 짧다면, 벽을 한 개까지 부수고 이동할 수 있다.

문제접근

• 가장 쉬운 풀이는 벽을 하나도 부수지 않은 상태에서 BFS, 모든 벽을 한번씩 부순 상황에서 BFS를 반복하면 되지만 시간초과에 무조건 걸린다!
  • 최대 999,998개의 벽이 있을 수 있고, 이때 BFS 한번에 대략 (2 x 999,000) 이상의 연산이 필요하고, 이를 999,998번 반복하면 10억이 넘는 연산이 필요하기 때문이다.
• 시작점부터 목표점까지 이동할 때, 각 좌표는 벽을 부순 상태로 이동해서 오거나 벽을 부수지 않고 이동해서 오는 경우가 있다.
• 따라서, 각 좌표는 벽을 부수고 이동했는지, 부수지 않고 이동했는지를 나타내는 상태변수 status 를 가진다.
• 각 칸까지 이동할 때 필요한 최단거리는 BFS를 통해 구하되, 벽을 부수고 온 경우와 부수지 않고 온 경우를 따로 가지고 있어야 한다.
  • 각 칸은 여러 경로에서 도달될 수 있다. 하지만, 필요한 정보는 벽을 부수고 왔을 때 최단 거리 와 벽을 부수지 않고 왔을 때 최단거리 만 알면 된다.
• 목적지에 도달했을 때, 2가지 경우 중 최단 거리의 값을 반환한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <memory.h>
using namespace std;

// status 는 벽을 부셨는지를 확인. 1이면 이미 벽을 하나 부순 상태
typedef struct _pos {
	int xpos, ypos, status;
} Pos;

int N, M;
vector<string> board;
// [x][y][0]: (x,y)까지 벽을 부수지 않았을 때 최소 비용
// [x][y][1]: (x,y)까지 벽을 부수고 왔을 때 최소 비용
int dist[1000][1000][2]; 
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int bfs(int sx, int sy) {
	memset(dist, 0, sizeof(dist));
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	dist[sx][sy][0] = 1;
	dist[sx][sy][1] = 1;
	
	while (!q.empty()) {
		Pos cpos = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cpos.xpos + dx[dir];
			int ny = cpos.ypos + dy[dir];
			int status = cpos.status;
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (board[nx][ny] == '0') {
				if (dist[nx][ny][status] == 0) {
					q.push({ nx, ny, status });
					dist[nx][ny][status] = dist[cpos.xpos][cpos.ypos][cpos.status] + 1;
				}
				else {
					if (dist[nx][ny][status] > dist[nx][ny][status] + 1) {
						q.push({ nx, ny, status });
						dist[nx][ny][status] = dist[cpos.xpos][cpos.ypos][cpos.status] + 1;
					}
				}
			}
			else if (board[nx][ny] == '1') {
				if (cpos.status == 0) {
					if (dist[nx][ny][1] == 0) {
						q.push({ nx, ny, 1 });
						dist[nx][ny][1] = dist[cpos.xpos][cpos.ypos][cpos.status] + 1;
					}
					else {
						if (dist[nx][ny][1] > dist[cpos.xpos][cpos.ypos][cpos.status] + 1) {
							q.push({ nx, ny, 1 });
							dist[nx][ny][1] = dist[cpos.xpos][cpos.ypos][cpos.status] + 1;
						}
					}
				}
			}
		}
	}
	if (dist[N-1][M-1][0] == 0 && dist[N-1][M-1][1] == 0) return -1;
	else if (dist[N - 1][M - 1][0] == 0) return dist[N - 1][M - 1][1];
	else if (dist[N - 1][M - 1][1] == 0) return dist[N - 1][M - 1][0];
	else return min(dist[N - 1][M - 1][0], dist[N - 1][M - 1][1]);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		board.push_back(str);
	}
	int answer = bfs(0, 0);
	cout << answer << endl;
	return 0;
}

• 백준에서는 입출력 함수는 통일해서 사용해주는 것이 좋다.
• N, M 을 입력 받을 때는 scanf 를 쓰고, 격자판을 입력받을 때는 cin 을 썼더니 18% 에서 틀렸습니다 가 나왔다.
• cin 으로 바꾸니 바로 통과…