How We Coding

[1162] 도로포장

BOJ/Shortest Path2018. 7. 28. 00:47

### Dijkstra ###


[1162] 도로포장 : http://boj.kr/1162


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF = 1e9;
 
typedef pair<int, int> P;
typedef pair<int, P> K;
 
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
 
    vector<P> g[10001];
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(P(b, c));
        g[b].push_back(P(a, c));
    }
 
    vector<vector<int> > dist(k+1, vector<int>(n+1, INF)); 
    dist[k][1] = 0; // kth pave, cur vertex
 
    priority_queue<K> pq;
    pq.push(K(0, P(1, k))); // dist, v, k
 
    bool visited[21][10001]={0}; 
  
    while(!pq.empty()) {
        int curV, curK;
        do {
            curV = pq.top().second.first;
            curK = pq.top().second.second; 
            pq.pop();
        } while(!pq.empty() && visited[curK][curV]);
  
        if(visited[curK][curV]) break;
        visited[curK][curV] = 1;
 
        for(auto &p : g[curV]) {
            int nextV = p.first;
            int d = p.second;
            
            if(dist[curK][nextV] > dist[curK][curV] + d) {
                dist[curK][nextV] = dist[curK][curV] + d;
                pq.push(K(-dist[curK][nextV], P(nextV, curK)));
            }
            if(curK-1 >= 0 && dist[curK-1][nextV] > dist[curK][curV]) {
                dist[curK-1][nextV] = dist[curK][curV];
                pq.push(K(-dist[curK-1][nextV], P(nextV, curK-1)));
            }
        }
    }
    
    int ans = 1e9;
    for(int i=0; i<=k; i++) {
        ans = min(ans, dist[i][n]);
    }
    
    printf("%d\n", ans);
    return 0;
}
 
cs

>> dist[k][i] : 포장을 k개 할 수 있는 상태에서 시작정점에서 i번 정점까지의 최단거리, 

    k값의 변화가 없는 겨우, 우리가 지금까지 구했던 다익스트라 dist 배열이다.


'BOJ > Shortest Path' 카테고리의 다른 글

[5917] 거의 최단경로  (0) 2018.07.26
[13424] 비밀 모임  (0) 2018.07.24
[10282] 해킹  (0) 2018.07.24

[5917] 거의 최단경로

BOJ/Shortest Path2018. 7. 26. 00:03

### Dijkstra ###


[5917] 거의 최단경로 : http://boj.kr/5917


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, s, e;
const int INF=1e9;
typedef pair<int, int> P;
 
vector<int> from[501];
 
void remove(vector<int> *from, int path[][501], int next)
{
    if(next == s) return ; 
 
    for(int i=0; i<from[next].size(); i++) {
        int cur = from[next][i];
        path[cur][next] = INF;
        remove(from, path, cur);
    }
 
}
 
int dijkstra(vector<P> *g, int path[][501])
{
    priority_queue<P> pq;
    pq.push(P(0, s));
 
    vector<int> dist(n+1, INF);
    dist[s] = 0;
 
    vector<bool> visited(n+1, 0);
 
    while(!pq.empty()) {
        int cur;
        do {
            cur = pq.top().second;
            pq.pop();
        } while(!pq.empty() && visited[cur]);
 
        if(visited[cur]) break;
 
        visited[cur] = 1;
 
        for(auto &p : g[cur]) {
            int next = p.first;
            int d = path[cur][next];
 
            if(dist[cur] + d == dist[next]) {
                from[next].push_back(cur);
            }
            else if(dist[next] > dist[cur] + d) {
                dist[next] = dist[cur] + d;
                pq.push(P(-dist[next], next));
                from[next].clear();
                from[next].push_back(cur);
            }
        }
    }
 
    return dist[e];    
}
 
int main()
{
    while(1) {
        scanf("%d%d", &n, &m);
        if(n == 0 && m == 0) break;
 
        scanf("%d%d", &s, &e);
 
        vector<P> g[501];
        int path[501][501]={0};
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            path[a][b] = c;
        }
 
        for(int i=0; i<n; i++)
            from[i].clear();
       
        int ans = dijkstra(g, path);
        if(ans == INF) {
            puts("-1");
            continue;
        }
        remove(from, path, e);
           
        ans = dijkstra(g, path);
        if(ans == INF) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}
 
cs

>> 푸는데 참 오래 걸렸다.

>> 결론적으로 다익스트라 두번 돌렸으며, 처음 돌릴때, from 벡터배열에 한 정점까지의 최단경로에 대한 이전 정점들에 대해 기록을 해두고,

>> remove 로 삭제. 그리고 다시 다익스트라를 한번 돌리면 된다. 


>> 주의할 것이 두가지 있었다. 처음 다익스트라를 돌렸을때 처음부터 갈수 없는 경로가 존재하는 경우에 대해 처리하는 것과

>> 다음으론 k 번 정점까지의 최단거리로 오는 방법이 한가지 가 아닌경우, 그 모든 경우에 대한 간선을 제거하는 것.!!


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
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
5 3
0 4
0 1 1
0 2 1
0 3 1
5 6
0 4
0 1 10
0 2 1
2 1 2
1 3 1
3 4 2
1 4 5
6 8 
0 5
0 1 1
1 2 1
2 3 1
3 4 1
4 5 1
0 2 2
2 5 10
0 5 5
0 0
 
cs


위 테스트 케이스에 대해 아래와 같이 정답이 나와야 한다.

마지막 테스트 케이스가 12가 나오면 여러가지 길이 있을 때, 한가지 길만 제거해서 생긴거라고 생각하면 된다.


5

-1

6

-1

15

-1

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[13424] 비밀 모임  (0) 2018.07.24
[10282] 해킹  (0) 2018.07.24

[13424] 비밀 모임

BOJ/Shortest Path2018. 7. 24. 16:29

### Dijkstra or Floyd ###


[13424] 비밀 모임 : http://boj.kr/13424



<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
const int INF=1e9;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, m;
        scanf("%d%d", &n, &m);
 
        vector<P> g[101];
        while(m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g[a].push_back(P(b, c));
            g[b].push_back(P(a, c));
        }
        
        int k, f;
        scanf("%d", &k);
        
        vector<int> ans(n+1, 0);
        for(int i=0; i<k; i++) {
            scanf("%d", &f);
            vector<bool> visited(n+1);
            vector<int> dist(n+1, INF);
            dist[f] = 0;
 
            priority_queue<P> pq;
            pq.push(P(0, f));
 
            while(!pq.empty()) {
                int cur;
                do {
                    cur = pq.top().second;
                    pq.pop();
                } while(!pq.empty() && visited[cur]);
 
                if(visited[cur]) break;
                visited[cur] = 1;
 
                for(auto &p : g[cur]) {
                    int next = p.first;
                    int d = p.second;
                    if(dist[next] > dist[cur] + d) {
                        dist[next] = dist[cur] + d;
                        pq.push(P(-dist[next], next));
                    }
                }
            }
            for(int i=0; i<=n; i++) {
                ans[i] += dist[i]; 
            }
        }
 
        int idx=1, minD=INF; 
        for(int i=1; i<=n; i++) {
            if(minD > ans[i]) {
                minD = ans[i];
                idx = i;
            }
        }
        printf("%d\n", idx);
    }
}
 
 
cs


>> 더 빠른시간에 수행된 다른사람들의 코드를 보니 플로이드로 풀었다.

>> n 제한이 100이라 플로이드로 돌려도 된다고 생각했지만, 다익스트라 공부중이라 다익스트라로 품

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[10282] 해킹  (0) 2018.07.24

[10282] 해킹

BOJ/Shortest Path2018. 7. 24. 15:22

### Dijkstra ###


[10282] 해킹 : http://boj.kr/10282


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long int lli;
const lli INF = 1e15;
typedef pair<int, int> P;
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n, d, c;
        scanf("%d%d%d", &n, &d, &c);
 
        vector<P> g[10001];
        for(int i=0; i<d; i++) {
            int a, b, s;
            scanf("%d%d%d", &a, &b, &s);
            // a 가 b를 의존
            // b 가 감염되면 s초 후에 a도 감염.
            g[b].push_back(P(a, s));
        }
    
        priority_queue<P> pq;
        pq.push(P(0, c)); 
 
        vector<bool> visited(n+1);
        vector<lli> dist(n+1, INF);
        dist[c] = 0;
 
        while(!pq.empty()) {
            int cur;
            do {
                cur = pq.top().second;
                pq.pop();
            } while(!pq.empty() && visited[cur]);
 
            if(visited[cur]) break;
            visited[cur] = 1;
            
            for(auto &p : g[cur]) {
                int next = p.first;
                int d = p.second;
                if(dist[next] > dist[cur] + d) {
                    dist[next] = dist[cur] + d;
                    pq.push(P(-dist[next], next));
                }
            }
        }
 
        int cnt=0, time=0;
        for(int i=1; i<=n; i++) {
            if(dist[i] != INF) {
                cnt++;
                if(time < dist[i])
                    time = dist[i];
            }
        }
        printf("%d %d\n", cnt, time);
    }
    return 0;
}
 
 
cs

>> 

'BOJ > Shortest Path' 카테고리의 다른 글

[1162] 도로포장  (0) 2018.07.28
[5917] 거의 최단경로  (0) 2018.07.26
[13424] 비밀 모임  (0) 2018.07.24

[3649] 로봇 프로젝트

BOJ/Parametric Search2018. 7. 24. 13:59

### Sort + Binary Search ###


[3649] 로봇 프로젝트 : http://boj.kr/3649


<소스코드>


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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int x, n;
vector<int> lego;
 
void solve()
{
    for(int i=0; i<n-1; i++) {
        int cur = lego[i];
        if(binary_search(lego.begin()+i+1, lego.end(), x-cur)) {
            printf("yes %d %d\n", cur, x-cur);
            return ;
        }
    }
    puts("danger");
}
 
int main()
{
    while(scanf("%d", &x) == 1) {
        scanf("%d", &n);
        lego = vector<int>(n);
        for(int i=0; i<n; i++) {
            scanf("%d", &lego[i]);
        }
 
        x *= 10000000;
        sort(lego.begin(), lego.end());
        solve();
    }
}
 
 
cs

>> 정렬 후 i 번째 값과 x-i번째 값이 [i+1, n-1] 구간에 존재하는지 확인. 

>> 시간복잡도 O(N*logN)

'BOJ > Parametric Search' 카테고리의 다른 글

[13905] 세부 (다른방법으로 풀어보기)  (0) 2018.07.24
[1939] 중량제한  (0) 2018.07.24

[13905] 세부 (다른방법으로 풀어보기)

BOJ/Parametric Search2018. 7. 24. 02:15

### Parametric Search + BSF ###


[13905] 세부 : http://boj.kr/13905


- 다익스트라 or MST+LCA 로도 풀 수 있다고 한다. 나중에 도전해봐야겠다..!!


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, w; };
 
int n, m;
int s, e;
vector<P> g[100001];
 
bool isPossible(int mid)
{
    queue<int> q;
    q.push(s);
 
    vector<bool> visited(n+1, 0);
    visited[s] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : g[cur]) {
            int next = p.to;
            int w = p.w;
            if(!visited[next] && mid <= w) {
                if(next == e) return 1;
                visited[next] = 1;
                q.push(next);
            }
        }
    }
    return 0;
}
 
int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &e);
 
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back((P){b, c});
        g[b].push_back((P){a, c});
    }
 
    if(s == e) return !printf("0\n");
 
    int S=1, E=1000000;
    while(S <= E) {
        int mid = (S+E)/2;
        if(isPossible(mid)) S = mid+1;
        else E = mid-1;
    }
    printf("%d\n", S-1);
    return 0;
}
 
cs

>> [1939] 중량제한 문제와 동일한 문제.

>> 근데 조건 한개가 다르다. 중량제한 문제는 출발지와 도착지가 서로 다르다고 명시가 되어 있는데, 위 문제는 그렇지 않다. 

>> 그래서 47 라인이 추가되었다.

'BOJ > Parametric Search' 카테고리의 다른 글

[3649] 로봇 프로젝트  (0) 2018.07.24
[1939] 중량제한  (0) 2018.07.24

[1939] 중량제한

BOJ/Parametric Search2018. 7. 24. 01:51

### Parametric Search + BFS ###


[1939] 중량제한 : http://boj.kr/1939


<소스코드>


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
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
struct P { int to, limit; };
 
int n, m;
int a, b, c;
vector<P> v[10001];
 
bool isPossible(int mid)
{
 
    queue<int> q;    
    q.push(a);
    
    vector<bool> visited(n+1, 0);
    visited[a] = 1;
 
    while(!q.empty()) {
        int cur = q.front(); q.pop();
 
        for(auto &p : v[cur]) {
            int next = p.to;
            int c = p.limit;
            if(!visited[next] && mid <= c) {
                if(next == b) return true;
                q.push(next);
                visited[next] = 1;
            }
        }
    }
    return false;
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    while(m--) {
        scanf("%d%d%d", &a, &b, &c);
        v[a].push_back((P){b, c});
        v[b].push_back((P){a, c});
    }
 
    scanf("%d%d", &a, &b);
    
    int s=1, e=1e9;
    while(s <= e) {
        int mid = (s+e)/2;
        if(isPossible(mid)) s = mid+1;
        else e = mid-1;
    }
    printf("%d\n", s-1); 
    return 0;
}
 
cs

>> 중량을 mid 로 설정했을 때, 이게 답이 될 수 있으면 탐색범위를 [mid+1, e] 로 좁혀간다. 

>> 답이될 수 없다면 [s, mid-1] 로 좁힌다.

'BOJ > Parametric Search' 카테고리의 다른 글

[3649] 로봇 프로젝트  (0) 2018.07.24
[13905] 세부 (다른방법으로 풀어보기)  (0) 2018.07.24

[2018] 수들의 합 5

BOJ/Math2018. 7. 22. 13:26

### Math ###


[2018] 수들의 합 : http://boj.kr/2018


<소스코드>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
 
 
int main()
{
    int n;
    int L=0, R=0;
    int ans=0, sum=0;
    scanf("%d", &n);
 
    if(n&1) {
        for(int i=3; i<=n; i+=2)
            if(n%i == 0) 
                ans++;
        ans++;
    }
    else {
        for(int i=2; i<=n; i+=2)
            if(n%i == 0 && (n/i)&1)
                ans++;
    }
    printf("%d\n", ans); 
    return 0;
}
cs


1) 홀수의 경우

- 무조건 두개의 연속된 합으로 표현이 가능하다.

- 홀수로 나누어 떨어지면 연속된 수들의 합으로 가능하다. 

   예를들어 9는 3으로 나누어 떨어지므로 3+3+3 으로 표현이 가능하고, 중앙값 기준으로 양옆은 1씩 주고 받으면 가능하다, 숫자가 더있으면, 2씩, 3씩, 주고받으면 된다.


2) 짝수인 경우

- 짝수로 나누어 떨어지고, 그 몫이 홀수이면 가능하다.

   예를 들어 10은 2로 나누어 떨어지고, 그 몫은 5이다. 5는 두개의 수인 2와 3으로, 1과 4로 표현이 가능하다. 즉 1, 2, 3, 4 의 연속된 수로 표현이 가능해진다.

[5639] 이진 검색 트리

BOJ/Data Structure2018. 7. 22. 12:30

### Tree Traversal ###


[5639] 이진 검색 트리 : http://boj.kr/5639


<소스코드>


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
#include <stdio.h>
 
int arr[10001];
 
void post(int L, int R)
{
    if(L >= R) return ;
    int k = L+1;
    while(k < R && arr[k] < arr[L]) k++;
    post(L+1, k);
    post(k, R);
    printf("%d\n", arr[L]);
}
 
int main()
{
    int n;
    int idx=0;
    while(scanf("%d", &n) == 1) {
        arr[idx++] = n;
    }
    
    post(0, idx);
    return 0;
}
 
cs

>> 전위위회의 결과를 준 상태에서 후위순휘의 결과를 출력하는 문제.

>> 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회를 한다. 

>> 후위순회를 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 순회를 한다.

>> 이진탐색트리는 왼쪽 서브트리는 루트보다 작은 키값들을 가지며, 오른쪽 서브트리는 루트보다 큰 키 값을 가진다. 

>> 이 특징을 이용하여 왼쪽 서브트리와 오른쪽 서브트리의 데이터들을 구분할 수 있다.

     그럼 왼쪽 서브트리의 데이터 - 오른쪽 서브트리의 데이터 - 루트 순으로 출력을 하면 된다. 

'BOJ > Data Structure' 카테고리의 다른 글

[1655] 가운데를 말해요  (0) 2018.07.22
[2529] 부등호  (0) 2018.07.22

[1655] 가운데를 말해요

BOJ/Data Structure2018. 7. 22. 12:03

### Priority Queue ###


[1655] 가운데를 말해요 : http://boj.kr/1655


<소스코드>


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
#include <cstdio>
#include <queue>
using namespace std;
 
int main()
{
    int n, k;
    scanf("%d", &n);
 
    priority_queue<int> minQ, maxQ;
    scanf("%d", &k);
    printf("%d\n", k);
    maxQ.push(k);
 
    for(int i=1; i<n; i++) {
        scanf("%d", &k);
        if(i&1) {
            if(maxQ.top() < k) minQ.push(-k);
            else {
                maxQ.push(k); minQ.push(-maxQ.top()); maxQ.pop();
            }
        }
        else {
            if(-minQ.top() > k) maxQ.push(k);
            else {
                minQ.push(-k); maxQ.push(-minQ.top()); minQ.pop();
            }
        }
        printf("%d\n", maxQ.top());
    }
    return 0; 
}
cs

>> max Heap 과 min Heap 을 이용하여, 그때그때마다 중앙값을 알 수 있다.


- input : 1 5 2 10 -99 7 5 순이라면


1) max Heap : 1

   min Heap : empty


2) max Heap : 1

    min Heap : 5


3) max Heap : 1 2

    min Heap : 5


4) max Heap : 1 2

    min Heap : 5 10


5) max Heap : -99 1 2

    min Heap : 5 10


6) max Heap : -99 1 2

    min Heap : 5 7 10


이런식으로 진행이 된다. 그때그때 마다의 중앙값은 max Heap 의 루트가 된다.




'BOJ > Data Structure' 카테고리의 다른 글

[5639] 이진 검색 트리  (0) 2018.07.22
[2529] 부등호  (0) 2018.07.22

티스토리툴바