www.acmicpc.net/problem/4485

 

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

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

www.acmicpc.net

 

다익스트라 기초에 2차원좌표가 추가되었습니다.

출발지점는 (0, 0)이고 도착지점은 (N - 1, N - 1)입니다.

그럼 (0, 0)에서 출발하여 각 칸까지의 최소비용을 구해주시면 됩니다.

 

 

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
77
#include <iostream>
#include <queue>
#include <cstring>
#define INF 1000000000
using namespace std;
 
typedef struct Point {
    int x;
    int y;
    int dis;
}Point;
 
int list[125][125], d[125][125];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N;
 
struct compare {
    bool operator()(Point a, Point b) {
        return a.dis > b.dis;
    }
};
 
void dijkstra() {
    priority_queue<Point, vector<Point>, compare> q;
    q.push({ 0,0,list[0][0] });
    d[0][0] = list[0][0];
    while (!q.empty()) {
        int x = q.top().x;
        int y = q.top().y;
        int dis = q.top().dis;
        q.pop();
 
        if (d[x][y] < dis) continue;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            int nextdis = dis + list[nx][ny];
            if (d[nx][ny] > nextdis) {
                d[nx][ny] = nextdis;
                q.push({ nx, ny, nextdis });
            }
        }
    }
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
}
 
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            d[i][j] = INF;
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    for (int t = 1; ; t++) {
        input();
        if (!N) return 0;
        init();
        dijkstra();
        cout << "Problem " << t << ": " << d[N - 1][N - 1] << '\n';
    }
}
 cs

'algorithm > dijkstra' 카테고리의 다른 글

boj 18352 특정 거리의 도시 찾기  (0) 2021.03.22
boj 14496 그대, 그머가 되어  (0) 2021.03.22

www.acmicpc.net/problem/18352

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

bfs와 다익스트라 두 가지방법 모두 사용하였습니다.

이 문제는 방향그래프이므로 u v 로 입력이 오면 u -> v로 받아야합니다.

 

먼저 다익스트라 알고리즘 방법으로는 가중치가 주어지지 않았기때문에 1로 두고 다익스트라 알고리즘을 이용하여 start에서 각 노드까지 최단거리를 다 구해줍니다.

최단거리가 K인 노드가 있으면 오름차순으로 출력해주고, 없으면 -1을 출력합니다.

 

bfs 방법으로는 start에서부터 시작하여 bfs를 K번 진행합니다.

bfs로 탐색하면서 각 노드까지의 거리를 갱신해줍니다.

최단거리가 K인 노드가 있으면 오름차순으로 출력해주고, 없으면 -1을 출력합니다.

 

다익스트라 사용
bfs 사용

 

다익스트라는 모든 정점까지의 최단거리를 다 구해주기 때문에 시간 상으로는 bfs가 훨씬 효율적입니다.

 

 

[dijkstra]

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
#include <iostream>
#include <queue>
#include <vector>
#define INF 1000000000
using namespace std;
 
vector<pair<int, int> > list[300001];
int d[300001];
int N, M, K, start;
 
void solve() {
    bool chk = false;
    for (int i = 1; i <= N; i++) {
        if (d[i] == K) {
            chk = true;
            cout << i << '\n';
        }
    }
 
    if (!chk) cout << "-1\n";
}
 
void dijkstra() {
    d[start] = 0;
    priority_queue<pair<int, int> > q;
    q.push({ start, 0 });
    while (!q.empty()) {
        int now = q.top().first;
        int dis = -q.top().second;
        q.pop();
 
        if (d[now] < dis) continue;
 
        for (int i = 0; i < list[now].size(); i++) {
            int next = list[now][i].first;
            int nextdis = dis + list[now][i].second;
 
            if (d[next] > nextdis) {
                d[next] = nextdis;
                q.push({ next, -nextdis });
            }
        }
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        d[i] = INF;
    }
}
 
void input() {
    int u, v;
    cin >> N >> M >> K >> start;
    init();
 
    while (M--) {
        cin >> u >> v;
        list[u].push_back({ v,1 });
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dijkstra();
    solve();
 
    return 0;
}
 cs

 

 

[bfs]

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
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
 
vector<int> list[300001];
queue<int> q;
int d[300001];
int N, M, K, start;
 
void solve() {
    bool chk = false;
    for (int i = 1; i <= N; i++) {
        if (d[i] == K) {
            chk = true;
            cout << i << '\n';
        }
    }
 
    if (!chk) cout << "-1\n";
}
 
void bfs() {
    q.push(start);
    d[start] = 0;
    for (int t = 1; t <= K; t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front();
            q.pop();
 
            for (int i = 0; i < list[x].size(); i++) {
                int next = list[x][i];
                if (d[next] != -1) continue;
                
                q.push(next);
                d[next] = t;
            }
        }
    }
}
 
void input() {
    int u, v;
    cin >> N >> M >> K >> start;
    while (M--) {
        cin >> u >> v;
        list[u].push_back(v);
    }
    memset(d, -1, sizeof(d));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    bfs();
    solve();
 
    return 0;
}
 cs

'algorithm > dijkstra' 카테고리의 다른 글

boj 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.23
boj 14496 그대, 그머가 되어  (0) 2021.03.22

www.acmicpc.net/problem/14496

 

14496번: 그대, 그머가 되어

첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 <= N <= 1,000, 1 <= M <= 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문자쌍

www.acmicpc.net

a를 b로 바꾸기 위해 필요한 최소 치환 횟수 -> a에서 b로 이동하기 위한 최단 거리

이렇게 바꾸어서 해결할 수 있습니다.

최단거리는 다익스트라를 이용합니다.

 

이 문제는 가중치가 주어지지 않으므로 모든 가중치는 1입니다.

입력으로 인접한 노드 번호 쌍이 주어지고 무방향 그래프입니다.

 

큐를 이용한 다익스트라를 사용하였고,

목적지인 b까지 도달할 수 있으면 d[des] 출력

목적지인 b까지 도달할 수 없으면 -1을 출력합니다.

 

 

다익스트라 기본 개념은 이곳에서 공부하였습니다.

blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234424646&categoryNo=128&parentCategoryNo=0&viewDate=&currentPage=5&postListTopCurrentPage=&from=postList&userTopListOpen=true&userTopListCount=5&userTopListManageOpen=false&userTopListCurrentPage=5

 

23. 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐...

blog.naver.com

 

 

[C++]

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1000000000
using namespace std;
 
vector<pair<int, int> > list[1001];
int d[1001];
int N, M, start, des;
 
void dijkstra() {
    d[start] = 0;
    priority_queue<pair<int, int> > q;
    q.push({ start, 0 });
    while (!q.empty()) {
        int x = q.top().first;
        int dis = -q.top().second;
        q.pop();
 
        if (d[x] < dis) continue;
 
        for (int i = 0; i < list[x].size(); i++) {
            int next = list[x][i].first;
            int nextdis = dis + list[x][i].second;
 
            if (d[next] > nextdis) {
                d[next] = nextdis;
                q.push({ next, -nextdis });
            }
        }
    }
    if (d[des] == INF) cout << "-1\n";
    else cout << d[des] << '\n';
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        d[i] = INF;
    }
}
 
void input() {
    int u, v;
    cin >> start >> des >> N >> M;
    init();
 
    while (M--) {
        cin >> u >> v;
        list[u].push_back({ v,1 });
        list[v].push_back({ u,1 });
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    dijkstra();
 
    return 0;
}
 cs

 

 

[Java]

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
77
78
79
80
81
82
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<int[]> list[] = new ArrayList[1001];
    static final int INF = 1000000000;
    static int d[] = new int[1001];
    static int N, M, start, des;
 
    static void dijkstra() {
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
 
        q.add(new int[] { start, 0 });
        d[start] = 0;
        while (!q.isEmpty()) {
            int now = q.peek()[0];
            int dis = q.poll()[1];
 
            if (d[now] < dis)
                continue;
 
            for (int i = 0; i < list[now].size(); i++) {
                int next = list[now].get(i)[0];
                int nextdis = dis + list[now].get(i)[1];
 
                if (d[next] > nextdis) {
                    d[next] = nextdis;
                    q.add(new int[] { next, nextdis });
                }
            }
        }
 
        if (d[des] == INF)
            System.out.println(-1);
        else
            System.out.println(d[des]);
    }
 
    static void init() {
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
            d[i] = INF;
        }
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        des = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        init();
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            list[u].add(new int[] { v, 1 });
            list[v].add(new int[] { u, 1 });
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dijkstra();
    }
}
 cs

'algorithm > dijkstra' 카테고리의 다른 글

boj 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.23
boj 18352 특정 거리의 도시 찾기  (0) 2021.03.22

+ Recent posts

티스토리툴바