반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘 :: http://www.crocus.co.kr/search/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C

2. 경로 추적


플로이드 워셜 알고리즘을 이용하여 문제를 기본적으로 접근한다.


문제 이름 자체도 플로이드 2이지만, 일단 정점이 100개라는 것을 생각한다면 당연히 플로이드로 접근 할 수 있는 문제이다.


그리고 플로이드 워셜을 통해 기본적인 최단 거리를 구해주고, 마지막으로 경로를 찾아내는 알고리즘을 통해 이 문제를 해결 할 수 있다.


경로 찾는 알고리즘은 주석을 통해 설명을 해 두었다.



소스 코드 : 


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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <algorithm>
 
#define INF 1000001
 
using namespace std;
 
int adj[101][101];
int dist[101][101];
int via[101][101];
 
// 경로 찾기
void reconstruct(int u, int v, vector<int> &path)
{
    // u->v로 가는 경유점이 없다면
    if (via[u][v] == 0)
    {
        // u를 담고
        path.push_back(u);
        // u와 v가 다르다면
        if (u != v)
            path.push_back(v); // v를 담는다.
        // u와 v가 같다면 경로는 자기 자신이다.
    }
 
    // u->v로 가는 경유점이 있다면
    else
    {
        // w에 경유점을 담아준다.
        int w = via[u][v];
 
        // u->w(경유점)으로 재귀를 호출한다.
        reconstruct(u, w, path);
        // 재귀에서 위의 if문에 의해 중첩되어 쌓이게 되는 것을 방지한다.
        path.pop_back();        
        // w->v로 재귀를 호출한다.
        reconstruct(w, v, path);
    }
}
int main()
{
    int V;
    scanf("%d", &V);
 
    int E;
    scanf("%d", &E);
 
    for (int i = 1; i <= V; i++)
        for (int j = 1; j <= V; j++)
            i == j ? adj[i][j] = 0 : adj[i][j] = INF;
 
    // 그래프 정보 입력
    for (int i = 0; i < E; i++)
    {
        int from, to, val;
        scanf("%d %d %d", &from, &to, &val);
 
        adj[from][to] = min(adj[from][to], val);
    }
 
    // 플로이드 워셜 알고리즘
    for (int k = 1; k <= V; k++)
        for (int x = 1; x <= V; x++)
            for (int y = 1; y <= V; y++)
            {
                if (adj[x][y] > adj[x][k] + adj[k][y])
                {
                    via[x][y] = k;
 
                    adj[x][y] = adj[x][k] + adj[k][y];
                }
            }
 
    // 플로이드 워셜을 통한 최단거리 표현
    for (int i = 1; i <= V; i++)
    {
        for (int j = 1; j <= V; j++)
            printf("%d ", adj[i][j]);
 
        printf("\n");
    }
 
    // 경로 찾기
    vector<int> path;
    for (int i = 1; i <= V; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            // i == j면 0 출력(자기 자신)
            if (i == j)
            {
                printf("0\n");
                continue;
            }
 
            reconstruct(i, j, path);
 
            // path에 받아온 경로를 출력한다.
            printf("%d ", path.size());
            for (int i = 0; i < path.size(); i++)
                printf("%d ", path[i]);
            printf("\n");
 
            path.clear();
        }
 
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[5427번] 불  (0) 2017.03.31
[4179번] Fire!  (4) 2017.03.31
[1168번] 조세퍼스 문제 2  (0) 2017.03.29
[1017번] 소수 쌍  (0) 2017.03.29
[9466번] 텀 프로젝트  (0) 2017.03.29

티스토리툴바