백준 2206(벽 부수고 이동하기)

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

2206번: 벽 부수고 이동하기

 

 

N, M 이 마무리이고, 벽은 한번만 뚫을 수 있으며, 최단 거리로 간다. 

 

모든 가능한 경우를 확인해서, 그 중 가장 짧은 거리를 출력한다. 

 

위 조건들을 보고 이 문제는 무조건 dfs다 라고 생각했다. 하지만 시간초과의 문제에 봉착했고, bfs로 돌렸다. 

dfs의 시간초과 여부를 계산하는게 아직 많이 어렵다. 아 근데 dfs로 풀린 코드도 있다. 이게 어떻게 가능했는지는 후에 서술하겠다. 

 

이 문제와 다른 bfs문제들의 차이점은 벽이 존재하는데 한번은 뚫을 수 있다는 것이었다. 

 

따라서 핵심은 벽을 한번만 뚫는 것을 어떻게 처리할지이다.

 

우선 bfs는 산탄총같이 한번에 사방으로 나가는 것이라서 각각의 독립적인 노선을 갖고 있다. 

따라서 만약 벽 변수의 선언을 함수 전체에 하게 된다면 각각 독립적인 노선이지만 벽 부수기 1회 사용을 했다 안 했다로 서로 영향을 주므로 그렇게 선언하면 안된다는 사실을 알 수 있다. 

 

그렇다면, 어떻게 해야할까. 

 

경로에 벽이 뚫린건지 아닌건지 알아야 한다. 내가 지나온 경로에서 벽 뚫기 찬스를 사용했다면, 그 노선에서는 쓸 수 없게끔 만들어야한다. 따라서 이전 경로에서 쓰였는지 안 쓰였는지까지 queue에 pair<pair<x좌표, y좌표> pair<경로횟수, 벽사용유무>> 로 저장하였다. 

 

그리고 가장 중요한 bfs의 특징은 최단거리 먼저 조사한다는 것이다. 그래서 어떤 지점을 최단거리로 밟았을 때, 그 지점을 밟은 경우는 벽을 뚫고 밟은 경우, 아닌 경우 두 가지로만 나뉜다. 

 

따라서 bool visited[x][y][wall]을 이용해서 사용하였다. 

 

아 이 과정에서 논리의 문제점이라고 생각한 경우를 보면,

 

A->B까지 가는데 C지점을 밟고 B로 간 경우(1)와 D지점을 밟고 간 경우(2) 가 같은 거리였을때,

(1)을 먼저 조사했는데, visited는 true로 변하고, D에서 C를 밟으면서 가는경로가 더 짧을 때 어떻게 될까를 생각했었다. 

 

하지만 결론은 논리에 문제가 없다는 것이다. 만약 C를 밟으면서 가는 경로가 더 짧다면, (1)에서 그냥 C에서 끝까지 가면 (2)보다는 확실하게 빨리 도착한다. 

 

 

bool done은 한 경로라도 도달하면, true로 하여서 원하는 결과를 출력하고 아닌 경우에는 -1을 출력하게끔 설정하였다. 

#include<iostream>
#include<string>
#include<queue>
#include<utility>
using namespace std;
#define MAX 1001

int N, M;
int mat[MAX][MAX];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue<pair<pair<int,int>, pair<int, bool> > > q;
pair<int, int> p;
bool done = false;
bool visited[MAX][MAX][2] = { false };

void bfs() {
	bool wall = false;
	int cnt;
	while (!q.empty()) {
		p.first = q.front().first.first;
		p.second = q.front().first.second;
		wall = q.front().second.second;
		cnt = q.front().second.first;
		q.pop();
		if (p.first == N && p.second == M) {
			cout << cnt << "\n";
			done = true;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int x = p.first + dx[i];
			int y = p.second + dy[i];
			if (x<1 || y<1 || x > N || y > M) continue;
			if (!visited[x][y][wall]) {
				if (!wall && mat[x][y]) {
					visited[x][y][wall] = true;
					q.push(make_pair(make_pair(x, y), make_pair(cnt+1, true)));
				}
				else if (!mat[x][y]) {
					visited[x][y][wall] = true;
					q.push(make_pair(make_pair(x, y), make_pair(cnt + 1, wall)));
				}

			}
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int j = 1; j <= M; j++) {
			mat[i][j] = str.at(j - 1) - '0';
		}
	}
	q.push(make_pair(make_pair(1, 1), make_pair(1, false)));
	bfs();
	if (!done) cout << -1 << "\n";
}