백준 1261 c++ -[PlusUltraCode]

[필자 사고]

 

다익스트라를 이용하여 푸는 문제이다.

 

이 문제에서 느낀점은 기존 다익스트라 문제에서 방문한 곳은 다시 방문 하지 않았다.

 

그 이유는 방문한 시점에서 이미 최단거리이기 때문에 시간복잡도를 더욱 효율적으로 하기 위해

 

방문하지 않았다. 다만 이 문제는 벽을 뿌신 개수의 최소값을 중점으로 두기 때문에 이미 방문한 곳이라도

 

벽을 부신 횟수를 비교해서 더욱 작은값이 있다면 새로 갱신해줘야 된다는 것이다.

 

또한 우선순위큐를 항상 pair<int,int> 로 사용했지만 직접 구조체를 만들어서 Node를 사용할 때는

 

정렬 함수를 따로 정의해줘야 된다. 안그러면 < 연산자에서 오류가 발생한다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include<queue>
#include<climits>
#include<algorithm>
using namespace std;

typedef struct Node {
	int Break;
	int sero;
	int garo;
	
}Node;
typedef struct cmp {
	bool operator()(Node a, Node b) {
		return a.Break > b.Break;
	}
};


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

int N, M;
vector<vector<int>> Arr;
vector<vector<int>> pathLoad;


void Input() {
	
	cin >> M >> N;
	Arr.resize(N);
	pathLoad.resize(N);
	string str;
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
		pathLoad[i].resize(M,INT_MAX);
	}
	
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			Arr[i][k] = str[k] - '0';
		}
	}
	

}

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}
void BFS() {
	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ 0,0,0 });
	pathLoad[0][0] = 0;
	while (!pq.empty()) {
		Node nowNode = pq.top();
		pq.pop();
		int nowSero = nowNode.sero;
		int nowGaro = nowNode.garo;
		if (nowSero == N - 1 && nowGaro == M - 1) {
			cout << nowNode.Break;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro)) {
				if (Arr[nextSero][nextGaro] == 1 &&
					pathLoad[nextSero][nextGaro] > pathLoad[nowSero][nowGaro] + 1) {
					pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro] + 1;
					pq.push({ pathLoad[nextSero][nextGaro] ,nextSero,nextGaro });
				}
				else if (Arr[nextSero][nextGaro] == 0 &&
					pathLoad[nextSero][nextGaro] > pathLoad[nowSero][nowGaro]) {
					pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro];
					pq.push({ pathLoad[nextSero][nextGaro] ,nextSero,nextGaro });
				}
			}
		}

	}

}




int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	BFS();
	
}