문제링크 : https://www.acmicpc.net/problem/2458


아이디어

  • 각 노드의 순서를 구하기
  • 만약 구체적인 순서를 묻지 않았다면 topo
    • topo는 구체적인 수치는 알 수 없음
  • floyd해서, 각 원소가 앞에있는지 위에있는지 확인
    • 이때, 확인되지 않은 원소가 있을경우, 모르는것

시간복잡도 계산

  • 플로이드 : O(N^3), 125e6 > 1e8 > 가능

자료구조

  • 앞인지 뒤인지 확인 배열 : int map[510][510]
    • -1 : 아직 모르는 상태
    • 0 : 작음, map[a][b] =0 = a가 b보다 작음
    • 1 : 큼, map[a][b] = 1 = a가 b보다 큼

코드(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
#include <iostream>
 
using namespace std;
 
int map[510][510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin>> N >> M;
    fill(&map[0][0], &map[509][510], -1);
    
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        map[a][b] = 0;
        map[b][a] = 1;
    }
    
    for(int i=1; i<=N; i++) map[i][i] = 1;
    
    // floyd 수행
    for(int k=1; k<=N; k++) {
        for(int j=1; j<=N; j++) {
            for(int i=1; i<=N; i++) {
                if(map[j][i] == -1) {
                    // j가 k보다 크고, k가 i보다 크면, j는 i 보다 큼
                    if(map[j][k] ==1 && map[k][i] == 1) map[j][i] = 1;
                    // j가 k보다 작고, k가 i보다 작으면, j는 i 보다 작음
                    if(map[j][k] ==0 && map[k][i] == 0) map[j][i] = 0;
                    
                }
            }
        }
    }
    
    int cnt=0;
    for(int j=1; j<=N; j++) {
        int ecnt = 0;
        for(int i=1; i<=N; i++) {
            if(map[j][i] == -1) break;
            ecnt++;
        }
        if(ecnt == N) cnt++;
    }
    
    cout << cnt << '\n';
    
    return 0;
}
 
cs

문제유형

  • 플로이드 - 몇번째 순서인지 구하는 문제
    • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
      • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
    • floyd로 모든 케이스 비교해서 구할 수 있음
      • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1

'알고리즘 > 백준' 카테고리의 다른 글

백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2580 스도쿠  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19

문제링크 : https://www.acmicpc.net/problem/18233


아이디어

  • 다익스트라를 두번써서 한번 거치고 가는것과 바로 가는것을 비교
  • 출발지에서 다익스트라 수행
  • 건우 위치에서 다익스트라 수행
  • 출발지 -> 마산 == 출발지 -> 건우 + 건우 -> 마산 을 확인

시간복잡도 계산

  • 다익스트라 : O(ElgE)
    • E : 1e4
    • 가능

자료구조

  • 인접리스트 vector<pair<int, int>> adj[5010]
    • 이떄 양방향임을 조심
  • 다익스트라 거리 배열 : int dist[5010]
    • chleorjfl : 1e4 * 5e3= 5e7 > INT 가능

코드(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
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> adj[5010];
const int inf = 1e8+10;
int dist[5010];
int dist2[5010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E,P; cin >> V >> E >> P;
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    fill(dist, dist+5010, inf);
    fill(dist2, dist2+5010, inf);
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 1번에서 출발
    dist[1] = 0;
    pq.push(make_pair(dist[1],1));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > nc + ec) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    dist2[P] = 0;
    pq.push(make_pair(dist2[P],P));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist2[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist2[ni] > nc + ec) {
                dist2[ni] = ec + nc;
                pq.push(make_pair(dist2[ni], ni));
            }
        }
    }
    
    if(dist[V] == dist[P] + dist2[V]) cout << "SAVE HIM\n";
    else cout << "GOOD BYE\n";
    
    
    
    return 0;
}
 
cs

문제유형

  • 한점 거쳐서 갈경우 최소거리인지 확인
    • E가 V에 비해 상대적으로 작으면(E<V^2), 다익스트라 두번쓰고
    • E가 V에 비해 상대적으로 크면(E > V^2), 플로이드 사용
    • 거쳐간 경우의 거리랑 최소값이 같은지 확인

'알고리즘 > 백준' 카테고리의 다른 글

백준 2580 스도쿠  (0) 2021.04.20
백준 2458 키 순서  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 2581 소수  (0) 2021.03.18

문제링크 : https://www.acmicpc.net/problem/1238


아이디어

  • X마을에서 각자 돌아가는 것은 다익스트라로 가능
  • 그럼 각자 마을에 X 모이는것도 다익스트라로 가능할까?
    • 경로를 반대로 저장해 놓으면 가능
  • X에 갈때의 경로와 돌아올때 사용할 경로를 각각 저장
    • X에 갈떄 경로는 다익스트라를 거꾸로 사용하기 위해 경로를 반대로 저장

시간복잡도 계산

  • 다익스트라 : O(ElgE)
    • E : M
    • O(MlgM) > 가능

자료구조

  • 경로 인접리스트 : vector<pair<int, int>> adj[1010]
    • 비용과 함꼐 입력
      • 다익스트라 비용 리스트 : int dist[1010]
    • 경로의 최대값이 별도로 나와있진 않지만, int로 가능할것으로 예상

코드(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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
const int inf = 1e8+10;
int dist[1010];
int dist_rev[1010];
vector<pi2> adj[1010];
vector<pi2> adj_rev[1010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dist, dist+1010, inf);
    fill(dist_rev, dist_rev+1010, inf);
    
    int N,M,X; cin >> N >> M >> X;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj_rev[b].push_back(make_pair(c,a));
    }
    
    // 가는것 먼저
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 도착지를 먼저 넣어 거꾸로 수행
    dist_rev[X] = 0;
    pq.push(make_pair(dist_rev[X], X));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist_rev[ei] != ec) continue;
        
        for(auto x : adj_rev[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist_rev[ni] > ec + nc) {
                dist_rev[ni] = ec + nc;
                pq.push(make_pair(dist_rev[ni], ni));
            }
        }
    }
    
    // 돌아오는것
    dist[X] = 0;
    pq.push(make_pair(dist[X], X));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    
    // 최대시간구하기
    int maxv = 0;
    for(int i=1; i<=N; i++) {
        maxv = max(maxv, dist[i] + dist_rev[i]);
    }
    
    cout << maxv << '\n';
    
    return 0;
}
 
 
cs

문제유형

  • 거꾸로 다익스트라
    • 한점까지 가는데 각각의 비용을 구하
    • 그래프 경로 입력부터 뒤집어서 입력

'알고리즘 > 백준' 카테고리의 다른 글

백준 2458 키 순서  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18

+ Recent posts

티스토리툴바