백준 2665(미로만들기)

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

2665번: 미로만들기

N^2의 격자에 흰색과 검은색이 존재한다. 검은색은 벽으로 이루어져서 지나갈 수 없다.

 

하지만 벽을 부술 수 있다. 최소 몇번의 벽을 부셔야 시작점에서 종료지점까지 갈 수 있는가

 

어디 지점에서 어디 까지 가는 방법 => dfs, bfs 

 

 

사실 먼저 dfs를 생각했다. dfs의 재귀함수로 몇 번의 벽을 부술지 기록하기가 더 쉽다고 생각했지만, 역시 문제점은 시간 만약에 dfs로 구현하게 된다면 벽이 보이는대로 다 부술테고 최소의 벽 부수기를 원하는 문제에는 알맞지 않다고 생각을 하였다. 

 

따라서 bfs와 priority_queue를 이용해서 벽을 더 적게 부순 경우를 먼저 조사하였다. 

 

bfs의 작동방법을 서술하면 

일단 네 방향으로 퍼진다. 

네 방향 중에 이동할 수 없는 경우인 경우 skip(index범위 초과, 이미 방문한 곳(벽 부순 횟수까지))

그 퍼진 곳 중에 벽이면 벽을 뚫고 priority_queue에 넣는다. 값에 벽 뚫은 횟수 +1

벽이 아닌 경우에 그대로 priority_queue에 넣는다.

queue가 빌때까지 반복

 

그리고 만약에 도착점에 도달했으면 벽 뚫은 횟수가 무조건 최솟값이므로 그 값을 출력.

 

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

priority_queue<pair<int , pair<int, int> > > pq;
pair<int, pair<int,int> > p;
int N, answer;
int room[MAX][MAX];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visited[MAX][MAX][MAX] = { false };

void bfs() {
	while (!pq.empty()) {
		p = pq.top();
		pq.pop();
		if (p.second.first == N - 1 && p.second.second == N - 1) {
			answer = -p.first;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int x = p.second.first + dx[i];
			int y = p.second.second + dy[i];
			if (x < 0 || y < 0 || x >= N || y >= N) continue;
			if (visited[-p.first][x][y]) continue;
			if (room[x][y] == 0) {
				pq.push(make_pair(p.first - 1, make_pair(x, y)));
				visited[-p.first + 1][x][y] = true;
			}
			else {
				pq.push(make_pair(p.first, make_pair(x, y)));
				visited[-p.first][x][y] = true;
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char a;
			cin >> a;
			room[i][j] = a - '0';
		}
	}

	pq.push(make_pair(0, make_pair(0, 0)));
	bfs();
	cout << answer << "\n";
}