Henu
개발냥발
Henu
전체 방문자
오늘
어제
  • 분류 전체보기 (411)
    • DevOps (52)
      • Kubernetes (19)
      • Docker (14)
      • AWS (3)
      • Nginx (4)
      • Linux (4)
      • ArgoCD (1)
      • CN (2)
      • NATS (0)
      • Git (5)
    • Back-End (30)
      • Django (18)
      • Spring (5)
      • JPA (1)
      • MSA (5)
    • CS (87)
      • SystemSoftware (20)
      • OS (25)
      • Computer Architecture (16)
      • Network (23)
      • Database (2)
    • Lang (21)
      • Java (9)
      • Python (4)
      • C# (8)
    • Life (12)
    • 블록체인 (2)
    • Algorithm (204)
      • BOJ (160)
      • 프로그래머스 (19)
      • LeetCode (4)
      • SWEA (1)
      • 알고리즘 문제 해결 전략 (8)
      • DS, algorithms (7)
      • Checkio (5)
    • IT (2)

블로그 메뉴

  • GitHub
  • 글쓰기
  • 관리자

공지사항

  • Free!

인기 글

태그

  • Kubernetes
  • docker
  • 다이나믹 프로그래밍
  • 백트래킹
  • boj
  • django
  • DFS
  • Network
  • 프로그래머스
  • BFS

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Henu

개발냥발

음주 운전 단속 (DRUNKEN)
Algorithm/알고리즘 문제 해결 전략

음주 운전 단속 (DRUNKEN)

2021. 7. 12. 15:28
 

algospot.com :: DRUNKEN

Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day,

www.algospot.com

플로이드-와샬

 

 

문제 설명

더보기

 

 

플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다.

이 과정에서 경유하는 정점을 1번부터 순서대로 추가하지만, 이 순서가 뒤죽박죽이 되어도 알고리즘은 성립한다!

그리고 이 문제는 간선의 값만 비교해서 최단 경로를 구하더라도 단속 시간에 의해서 오히려 오래 걸릴 수 있기 때문에 어떤 점을 경유하는지가 더 중요하다.

 

a에서 b로가는 최소 예상 시간을 저장하는 2차원 배열을 하나 설정한다.

 

먼저 정점을 하나도 경유하지 않고 a에서 b로 다이렉트로 가는 최단 경로를 구한다.

시작점과 도착점에서 단속을 하지 않기 때문에 a와 b가 같은경우에는 0이 되고 a에서 b로가는길은 단순히 처음에 주어진 입력과 같게 된다.

 

그리고 각 정점별 단속시간을 오름차순으로 정렬해 준다.

단속에 시간이 적게 걸리는 정점부터 경유를 하면 항상 단속시간이 최소화된 값으로 플로이드 알고리즘을 수행하기 때문에 최단 경로를 올바르게 구할 수 있다.

 

본격적으로 a에서 b로가는 최단 경로를 구해보자

우선 3중 for문에서 일반적인 플로이드 최단거리를 구하듯이 a에서 b로가는 최단 거리를 갱신해 준다.

그리고 최소 예상 시간을 저장하는 배열에는

<기존에 구한 a에서 b로가는 최단 시간 vs a에서 b로가는데 현재 경유점의 단속시간을 더한 시간 값> 을 비교해서 더 작은 값으로 갱신해준다.

 

 

코드

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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int V, E, T;
pii crackdown[501];
int Graph[501][501];
int res[501][501];
pii output[1001];
 
void input(){
    int a, b, c;
    cin >> V >> E;
    for(int i = 1; i <= V; i++){
        cin >> a;
        crackdown[i] = {a, i};
    }
    
    for(int r = 1; r <= V; r++){
        for(int c = 1; c <= V; c++){
            Graph[r][c] = INF;
            res[r][c] = INF;
        }
    }
    for(int i = 0; i < E; i++){
        cin >> a >> b >> c;
        Graph[a][b] = c;
        Graph[b][a] = c;
    }
    
    cin >> T;
    for(int i = 0; i < T; i++){
        cin >> a >> b;
        output[i] = {a, b};
    }
}
 
void solve(){
    for(int i = 1; i <= V; i++){
        for(int j = 1; j <= V; j++){
            if(i == j) res[i][j] = 0;
            else res[i][j] = Graph[i][j];
        }
    }
    
    sort(crackdown+1, crackdown+V+1);
    
    for(int i = 1; i <= V; i++){
        int via = crackdown[i].second;
        int delay = crackdown[i].first;
        for(int r = 1; r <= V; r++){
            for(int c = 1; c <= V; c++){
                Graph[r][c] = min(Graph[r][c], Graph[r][via] + Graph[via][c]);
                res[r][c] = min(res[r][c], Graph[r][via] + delay + Graph[via][c]);
            }
        }
    }
    
    for(int i = 0; i < T; i++){
        cout << res[output[i].first][output[i].second] << "\n";
    }
    
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}
 
Colored by Color Scripter
cs

 

'Algorithm > 알고리즘 문제 해결 전략' 카테고리의 다른 글

근거리 네트워크 (LAN)  (0) 2021.07.18
선거 공약 (PROMISES)  (0) 2021.07.18
소방차 (FIRETRUCKS)  (0) 2021.07.11
Sorting Game (SORTGAME)  (0) 2021.06.29
강한 연결 요소 (SCC) - 타잔 알고리즘  (0) 2021.06.28
    'Algorithm/알고리즘 문제 해결 전략' 카테고리의 다른 글
    • 근거리 네트워크 (LAN)
    • 선거 공약 (PROMISES)
    • 소방차 (FIRETRUCKS)
    • Sorting Game (SORTGAME)

    티스토리툴바