반응형

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

 

4485번: 녹색 옷 입은 애가 젤다지?

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. N을 입력받고 visited 배열을 초기화해줍니다.

 

2. pos struct를 만들어 y좌표, x좌표, 현재까지 잃은 루피 cur을 저장합니다.

 

3. dijkstra를 통해 가장 적게 루피를 잃고 나오는 경우의 값을 ans에 저장한 후 출력합니다.

 

[ 소스코드 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
using namespace std;
 
int N;
int arr[130][130];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[130][130];
 
struct pos {
    int y;
    int x;
    int cur;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cur < right.cur;
    }
};
 
int main()
{
    int cnt = 1;
 
    while (1) {
        scanf("%d", &N);
        memset(visited, 0, sizeof(visited));
 
        if (N == 0) break;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        int ans = 0;
 
        priority_queue<pos, vector<pos>, cmp> pq;
        pq.push({ 0,0,arr[0][0] });
 
        while (!pq.empty()) {
            int y = pq.top().y;
            int x = pq.top().x;
            int cur = pq.top().cur;
            pq.pop();
 
            if (visited[y][x] == 1) continue;
            visited[y][x] = 1;
 
            if (y == N - 1 && x == N - 1) {
                ans = cur;
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int yy = y + dy[i];
                int xx = x + dx[i];
 
                if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                    if (visited[yy][xx] != 1) {
                        pq.push({ yy,xx,cur + arr[yy][xx] });
                    }
                }
            }
        }
 
        printf("Problem %d: %d\n", cnt, ans);
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 2151번 - 거울 설치 (C++)  (0) 2022.11.22
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20

+ Recent posts

티스토리툴바