백준2665 - 미로만들기

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

2665번: 미로만들기

다익스트라를 이용하여 수행하였다. bfs를 이용하면 방문한 곳을 재방문하지 않기 때문에 다익스트라로 수행하여 풀었다. 

 

과거에 내가 가려 하는 곳까지 뚫은 벽의 갯수보다 현재 내가 가려는 곳까지 벽의 갯수가 적으면 현재로 내가 가려하는 곳까지의 벽의 갯수를 갱신한다.

 

전에 풀었던 문제와 다르게 먼저 도달하는 여부와 상관없이 벽의 갯수만 카운팅하면 되어 큐를 사용하였다.

#include <iostream>
#include <queue>
#include <string>
#define MAX 51
#define INF 1000000
using namespace std;

int n;
string s;
int mat[MAX][MAX];
int d[MAX][MAX];

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//모든 위치의 비용을 INF로 세팅
void setting() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			d[i][j] = INF;
		}
	}
}

//도달한 곳까지의 벽의 갯수를 세는 함수
void dijkstra() {
	queue<pair<int, int>> q; //다익스트라르 수행할 좌표공간을 저장
	q.push(pair<int, int>(1, 1)); //출발 위치는 (1, 1)
	d[1][1] = 0; //출발 위치 비용은 0

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (1 <= nx && nx <= n && 1 <= ny && ny <= n) { //좌표공간 내의 유효범위이면
				if (mat[nx][ny] == 0) { //벽인 경우면
					if (d[nx][ny] > d[x][y] + 1) { //이전 과정으로 도달하려는 곳까지의 벽의 총 갯수가 현재까지 벽을 뚫고 지나가는 갯수 + 현재 부숴야 하는 벽의 갯수보다 크면
						d[nx][ny] = d[x][y] + 1; //현재 과정을 통해 얻은 벽의 갯수로 도달하려는 곳의 벽의 갯수를 갱신
						q.push(pair<int, int>(nx, ny)); //큐에 삽입
					}
				}
				else {
					if (d[nx][ny] > d[x][y]) { //이전 과정으로 도달하려는 곳까지의 벽의 총 갯수가 현재까지 벽을 뚫고 지나가는 갯수보다 크면
						d[nx][ny] = d[x][y]; //현재 과정을 통해 얻은 벽의 갯수로 도달하려는 곳의 벽의 갯수를 갱신
						q.push(pair<int, int>(nx, ny)); //큐에 삽입
					}
				}
			}
		}
	}
}

int main() {
	setting();

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			mat[i][j + 1] = s[j] - '0';
		}
	}

	dijkstra();

	cout << d[n][n];

	return 0;
}