[백준 BOJ][C++]1261번 알고스팟 풀이: BFS

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

1261번: 알고스팟

 

 이 문제는 BFS를 이용하여 해결할 수 있습니다. 

 

 queue에 들어갈 노드 정보인 구조체 node는 해당 방의 위치 x, y와 해당 방까지의 벽을 부순 횟수 cnt로 이루어져 있습니다. 

 

 visit[y][x][c] 는 (x, y) 방 위치까지의 경로에서 벽을 부슨 횟수가 c인 노드의 방문 여부를 나타냅니다. 

 

 원래는 미로의 마지막 방으로 가는 모든 경로를 탐색하여 cnt의 최솟값을 계속 갱신하는 방법으로 했으나 시간초과가 발생하여 큐를 우선순위큐로 변경하였습니다. 

 

 벽을 부순 가장 최솟값을 얻기 위해, 우선순위큐를 이용하였고 노드의 위치가 미로의 끝 방의 위치와 같다면 그 즉시 cnt를 반환하고 탐색을 종료합니다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

#define MAX 101

int n, m;
bool visit[MAX][MAX][MAX*MAX] = { false, };
int map[MAX][MAX];

typedef struct node {
	int x;
	int y;
	int cnt;
};

struct compare {
	bool operator()(node a, node b) {
		return a.cnt > b.cnt;
	}
};

int bfs() {
	
	priority_queue < node, vector<node>, compare > q;

	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };

	visit[0][0][0] = true;
	q.push({ 0, 0, 0 });

	while (!q.empty()) {
		node curr = q.top();
		q.pop();

		if (curr.x == m - 1 && curr.y == n - 1) {
			return curr.cnt;
		}

		for (int i = 0; i < 4; i++) {
			int tx = dx[i] + curr.x;
			int ty = dy[i] + curr.y;

			if (tx < 0 || tx >= m || ty < 0 || ty >= n)
				continue;

			if (map[ty][tx] == 0 && !visit[ty][tx][curr.cnt]) {
				visit[ty][tx][curr.cnt] = true;
				q.push({ tx, ty, curr.cnt });
			}
			else if (map[ty][tx] == 1 && !visit[ty][tx][curr.cnt + 1]) {
				visit[ty][tx][curr.cnt + 1] = true;
				q.push({ tx, ty, curr.cnt + 1});
			}
		}
	}

}

int main(void) {

	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		string num;
		cin >> num;
		for (int j = 0; j < m; j++) {
			map[i][j] = num[j] - 48;
		}
	}

	cout << bfs();

	return 0;
}