[BAEKJOON] 1261 알고스팟

#include <iostream> #include <vector> #include <fstream> #include <algorithm> #include <queue> #include <string> #include <functional> using namespace std; #define PAIR pair<int, pair<int, int>> #define MAXNUM 123456789 int main() { int row_size, col_size; cin >> row_size >> col_size; vector<pair<int, int>>movement; vector<vector<int>> dist = vector<vector<int>>(col_size, vector<int>(row_size, MAXNUM)); vector<string>map = vector<string>(col_size); priority_queue <PAIR, vector<PAIR>, greater<PAIR>> cache; movement.push_back(make_pair(1, 0)); movement.push_back(make_pair(0, 1)); movement.push_back(make_pair(-1, 0)); movement.push_back(make_pair(0, -1)); for (int j = 0; j < col_size; j++) cin >> map[j]; cache.push(make_pair(0, make_pair(0, 0))); while (!cache.empty()) { int cost = cache.top().first, x = cache.top().second.first, y = cache.top().second.second; cache.pop(); if (x == col_size - 1 && y == row_size - 1) { cout << cost << endl; break; } if (dist[x][y] < cost) continue; //중복제거 for (int j = 0; j < 4; j++) { int temp_x = x + movement[j].first, temp_y = y + movement[j].second; if (temp_x >= 0 && temp_x < col_size && temp_y >= 0 && temp_y < row_size) { if (dist[temp_x][temp_y] > (cost + map[temp_x][temp_y] - '0')) { dist[temp_x][temp_y] = (cost + map[temp_x][temp_y] - '0'); cache.push(make_pair((cost + map[temp_x][temp_y] - '0'), make_pair(temp_x, temp_y))); } } } } }

2차 배열에서 다익스트라 알고리즘을 사용하는 것이다.

다익스트라 알고리즘을 사용한다는 것은 구글 검색을 통해서 알았다..

요새 문제를 끝까지 풀지도 않고 그냥 어영부영 넘어가려고 하는 것 같다..

처음에는 문제를 틀렸다

왜냐하면 중복제거를 안해줬기 때문이다 즉 온 길을 다시 돌아가는 조건을 추가하지 않은 것이다.

따라서 중간에 continue를 넣는다는 것을 알았다

visit를 사용하는 대신 cost>dist[x][y]을 사용하였다