[백준 1261 | C++] 알고스팟 :: 다익스트라

• 문제 링크 : 1261번: 알고스팟
• 관련 태그 : 그래프 이론, 그래프 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색
• 관련 문제 : 4485번: 녹색 옷 입은 애가 젤다지?
• 관련 자료 : 2025.01.11 - [BOJ] - [백준 4485 | C++] 녹색 옷 입은 애가 젤다지? :: 다익스트라

[백준 4485 | C++] 녹색 옷 입은 애가 젤다지? :: 다익스트라

 

풀이

첨부한 젤다 문제랑 모델링 방식이 똑같았습니다. 자세한 설명은 해당 포스트를 참고해주세요.

결론은 간선의 가중치를 해당 간선이 향하는 노드에 저장된 비용을 부여하면 됩니다. 

 

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m, n;	// n : 행, m : 열
const int INF = 1 << 30;

int dijkstra(vector<vector<pair<int, int>>>& g);

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n;
	vector<vector<char>> v(n, vector<char>(m, 0));
	vector<vector<pair<int, int>>> g(m * n);

	for (int r = 0; r < n;r++) {
		for (int c = 0;c < m;c++) {
			cin >> v[r][c];
		}
	}


	for (int r = 0; r < n;r++) {
		for (int c = 0;c < m;c++) {
			int idx = r * m + c;
			for (int i = 0; i < 4; i++) {
				int new_r = r + dr[i];
				int new_c = c + dc[i];
				int new_idx = new_r * m + new_c;

				if (new_r < 0 || new_r >= n || new_c < 0 || new_c >= m) continue;
				if (v[new_r][new_c] == '1') {
					g[idx].push_back({ 1, new_idx });	// cost, node
				}
				else {
					g[idx].push_back({ 0, new_idx });
				}
			}
		}
	}

	cout << dijkstra(g);
}

int dijkstra(vector<vector<pair<int, int>>> &g) {
	vector<int>dist(n * m, INF);
	priority_queue<pair<int, int>>pq;

	pq.push({ 0, 0 });	// 0번 정점 출발
	dist[0] = 0;

	while (!pq.empty()) {
		int cur_dist = -pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();

		if (cur_dist != dist[cur_node]) continue;
		for (auto x : g[cur_node]) {
			int nxt_dist = cur_dist + x.first;
			int nxt_node = x.second;

			if (nxt_dist < dist[nxt_node]) {
				dist[nxt_node] = nxt_dist;
				pq.push({ -nxt_dist, nxt_node });
			}
		}
	}

	return dist[n * m - 1];
}