백준 2665 c++ -[PlusUltraCode]

[필자 사고]

이 문제는 2차원 배열에서 다익스트라 알고리즘을 사용하는 교과서적인 문제이다

 

간단하게 문제를 설명하면 자신이 벽을 부신 횟수를 우선순위큐에 넣어 벽을 부신 수가 적은 index부터

 

접근하여 문제를 해결해 나가면 쉽게 풀 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
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;
vector<vector<int>> Arr;
vector<vector<bool>> visited;

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

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Dijkstra() {
	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ 0,0,0 });
	while (!pq.empty()) {
		int nowSero = pq.top().sero;
		int nowGaro = pq.top().garo;
		int nowBreak = pq.top().Break;
		pq.pop();
		if (nowSero == N - 1 && nowGaro == N - 1) {
			cout << nowBreak;
			return;
		}
		if (visited[nowSero][nowGaro] == true)continue;
		visited[nowSero][nowGaro] = true;
		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] == 0) {
					pq.push({ nowBreak + 1,nextSero,nextGaro });
				}
				else {
					pq.push({ nowBreak,nextSero,nextGaro });
				}
			}
		}
	}

}

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