[ 백준 / 4485 ] 녹색 옷 입은 애가 젤다지? (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : BFS , 다익스트라 
풀이 시간 : 49분 

문제 풀이 

목적지까지 가는 데 뺏기는 루피의 최솟값을 구하는 문제이다. 처음에는 단순히 BFS 돌리면 되겠지 ~ 하고 룰루랄라 돌렸는데 아뿔싸 ! BFS를 돌리는 도중, 방문처리를 하게 되면 다른 노드에서 온 값에 대해 처리를 하지 못해 빼앗기는 최소 루피를 구할 수 없게 된다.

따라서 나는 다익스트라 알고리즘을 사용해보았다. 다익스트라 알고리즘이란 ? 최단거리를 찾기 위한 알고리즘 중 하나이며, 현재 값과 가중치를 더해 새로운 값과 비교하고, 우선순위큐를 사용하므로 최단거리를 찾을 수 있다. 

 

그런데, 우선순위큐를 구현하고, 실행하자 바로 시간초과가 뜨는 것이 아닌가 ! 왜와이 ! 나는 내 생각이 틀리지 않았다고 판단했는데 시간초과가 떠버렸다.

이유가 뭐지 .. 생각하다가 아무리 생각해도 답이 안나오길래 우리의 친구 우리의 동반자 챗지피티 선생님에게 물어봤다 .. ㅎㅎ

그 이유는, priority_queue의 cmp 함수에서 너무 많은 연산이 일어난다는것이었다.

맞다. 나는 c++을 접하면서 무조건적으로 cmp 함수를 사용해야 하는 줄 알았다. 하지만 이 과정에서 많은 연산이 발생하게 된다는 사실을 간과하지 못했다. 따라서, 이를 단순히 priority_queue의 내부 비교문을 통해서 동작하도록 `pair<int, pair<int, int>>`로 수정해준 뒤 다시 다익스트라를 돌리자, 시간초과에서 벗어날 수 있었다 ! 

 

코드1. BFS

/*
젤다는 공주다 !

N x N 
상하좌우 인접한 곳으로 한 칸 씩 이동 가능
잃은 금액을 최소로 하여 동굴 건너편까지 가야한다. ( N - 1, N - 1)

링크가 잃을 수밖에 없는 최소 금액은 ?
*/

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

#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
#define INF 10 * 126 * 126

using namespace std;

int n, tmp;
int ans;
vector<vector<int>> graph;
int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };
int visited[126][126] = { 0, };

void bfs(int sr, int sc, vector<vector<int>> graph) {
	queue<pair<int, int>> q;
	visited[sr][sc] = graph[sr][sc];
	q.push({ sr, sc });

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		// 가지치기
		if (visited[r][c] >= ans) continue;

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if (0 <= nr && nr < n && 0 <= nc && nc < n) {
				// 도착했으면 값 업데이트
				if (nr == n - 1 && nc == n - 1) {
					ans = min(ans, visited[r][c] + graph[nr][nc]);
					continue;
				}
				if (visited[nr][nc] > visited[r][c] + graph[nr][nc]) {
					visited[nr][nc] = visited[r][c] + graph[nr][nc];
					q.push({ nr, nc });
				}
			}
		}
	}
}


int main() {
	int t = 0;
	while (1) {
		t++;
		cin >> n;
		vector<vector<int>> graph(n);
		if (!n) break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> tmp;
				graph[i].push_back(tmp);
				visited[i][j] = INF;
			}
		}

		ans = INF;
		bfs(0, 0, graph);

		cout << "Problem " << t << ": " << ans << '\n';

	}

	return 0;
}

코드 2. 다익스트라

/*
젤다는 공주다 !

N x N
상하좌우 인접한 곳으로 한 칸 씩 이동 가능
잃은 금액을 최소로 하여 동굴 건너편까지 가야한다. ( N - 1, N - 1)

링크가 잃을 수밖에 없는 최소 금액은 ?
*/

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

#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
#define INF 10 * 126 * 126

using namespace std;


int n, tmp;
int ans;
vector<vector<int>> graph;
int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };
int visited[126][126] = { 0, };



void dijkstra(int sr, int sc, vector<vector<int>> graph) {
	priority_queue<pair<int, pair<int, int>>> pq;
	visited[sr][sc] = graph[sr][sc];
	pq.push({ -graph[sr][sc], {sr, sc} });

	while (!pq.empty()) {
		int v = -pq.top().first;
		int r = pq.top().second.first;
		int c = pq.top().second.second;
		pq.pop();

		// 도착했으면 값 업데이트
		if (r == n - 1 && c == n - 1) {
			ans = v;
			return;
		}


		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if (0 <= nr && nr < n && 0 <= nc && nc < n) {
				int nv = v + graph[nr][nc];
				if (nv < visited[nr][nc]) {
					visited[nr][nc] = nv;
					pq.push({ -nv, {nr, nc} });
				}
			}
		}
	}
}


int main() {
	int t = 0;
	while (1) {
		t++;
		cin >> n;
		vector<vector<int>> graph(n);
		if (!n) break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> tmp;
				graph[i].push_back(tmp);
				visited[i][j] = INF;
			}
		}

		ans = INF;
		dijkstra(0, 0, graph);

		cout << "Problem " << t << ": " << ans << '\n';

	}

	return 0;
}

 

+ 추가로 이전에 파이썬으로 한 번 풀었던 문제여서, 파이썬 풀이 코드도 올려보도록 하겠다. 다익스트라 알고리즘을 사용하였다.

'''
단순 dijkstra
루피가 작은 쪽으로만 이동하면 된다.
'''

import heapq, sys
input = sys.stdin.readline

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def dijkstra(srow, scol):
    pq = []
    heapq.heappush(pq, (cave[srow][scol], srow, scol))
    visited = [[int(1e9)] * N for _ in range(N)]
    visited[srow][scol] = cave[srow][scol]

    while pq:
        cur_cost, row, col = heapq.heappop(pq)

        if (row, col) == (N - 1, N - 1):
            return cur_cost

        for d in range(len(dr)):
            nrow, ncol = row + dr[d], col + dc[d]
            if 0 <= nrow < N and 0 <= ncol < N:
                new_cost = cur_cost + cave[nrow][ncol]
                if visited[nrow][ncol] > new_cost:
                    visited[nrow][ncol] = new_cost
                    heapq.heappush(pq, (new_cost, nrow, ncol))

tc = 1
while True:
    N = int(input())
    if not N:
        break
    cave = [list(map(int, input().split())) for _ in range(N)]
    print(f'Problem {tc}: {dijkstra(0, 0)}')
    tc += 1

배운 점 

역시 ,,, 문제를 많이 풀어봐야한다고 생각했다. 하긴, 파이썬도 모든 문제를 알잘딱하게 풀기까지 시간이 꽤나 걸렸으니, c++의 라이브러리들에 익숙해지는데도 시간이 꽤 걸릴 것이라고 생각된다 ㅎㅎ 정-진