#문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

#작성 코드

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
 
int n, k;
vector<pair<int, int> > item;
int d[100][100001];                        // 인덱스 0~99 사용 
 
void input(){
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; i++){
        int w, v;
        scanf("%d %d", &w, &v);
        item.push_back(make_pair(w, v));
    }
}
 
int knapsack(int cur, int cap){
    if( cur == n ) return 0;
    int tmp = d[cur][cap];
    // 이 값이 이미 계산된 값이라면 저장된 값을 리턴 
    if( tmp != 0 ) return tmp;
    
    // 여유무게 >= 이번 아이템 무게일때
    // 이번 아이템을 담는 선택 vs 담지 않는 선택 중 value가 최대가 되는 선택을 한다. 
    if( cap>=item[cur].first ){
        tmp = max( knapsack(cur+1, cap-item[cur].first)+item[cur].second,
                    knapsack(cur+1, cap));
    }
    // 여유무게 < 이번 아이템 무게이면
    // 이 아이템은 절대로 담을 수없으므로 다음 아이템을 탐색한다. 
    else{
        tmp = knapsack(cur+1, cap);
    }
    return d[cur][cap] = tmp;
}
 
void solve(){
    printf("%d\n", knapsack(0, k));
}
 
int main(){
    input();
    solve();
    return 0;
}
 cs

 

bottom up

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 <bits/stdc++.h>
using namespace std;
 
int N;
int K;
int item[100][2];
int max_pack=0;
 
int main(){
    cin>>N>>K;
    for(int i=0; i<N; i++){
        cin>>item[i][0]>>item[i][1];
    }
    int *pack = new int[K+1];
 
    pack[0] = 0;
    for(int i=0; i<N; i++){
        for(int x=K; x>=0; x--){
            if(x-item[i][0]>=0)
                pack[x] = max(pack[x], pack[x-item[i][0]]+item[i][1]);
            max_pack = max(max_pack, pack[x]);
        }
    }
    cout<<max_pack;
    return 0;
}
 cs

?! 왜 무게를 0부터 시작했을땐 오류가 나고, K부터 시작해서 줄여나가면 제대로 되는거지

##

이번 물건을 배낭에 담을 수 있을 때 담는 선택, 담지 않는 선택 둘 다를 고려해야 하는 점이 중요한것같다.

 

아래 글을 참고해서 조금 더 공부해야지!

http://blog.naver.com/PostView.nhn?blogId=frankjune&logNo=221341520199&parentCategoryNo=&categoryNo=38&viewDate=&isShowPopularPosts=false&from=postView
아주 도움이 되었다. TOP-DOWN방식과 BOTTOM-UP방식 DP의 효율성에 대해서 생각해보아야겠다.
저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11657번 :: 타임머신  (0) 2019.12.15
BOJ 11047번 :: 동전 0  (0) 2019.12.15
BOJ 9370번 :: 미확인 도착지  (0) 2019.12.13
BOJ 1912번 :: 연속합  (0) 2019.12.09
BOJ 9251번 :: LCS  (0) 2019.12.09

#문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는 지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

  • 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.

  • 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)

  • 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.

  • 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

  • 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

 

#작성 코드

1.

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
#include <iostream>
#include <cstdio> 
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int INF = 2000000000;
int T;                // 테스트케이스개수 
int n, m, t;        // 도시개수, 도로개수, 목적지후보개수 
int s, g, h;        // 출발지, 경유지1, 경유지2 
vector<pair<int, int> > city[2001];        // 도시 간 연결 저장 
vector<int> dest;                        // 목적지 후보들 저장
 
vector<int> dijkstra(int start){
    priority_queue<pair<int, int> > pq;
    // -거리, 도시번호, 두 경유지 경유 여부 저장.
    vector<int> shortest(n+1, INF);
    // 출발-출발거리 :0, 출발지점, 경유지 사이 도로 지났는지 큐에 push 
    pq.push(make_pair(0, start));
    shortest[start] = 0;
    
    while(!pq.empty()){
        int now = pq.top().second;
        int di = -pq.top().first;
        pq.pop();
        
        if( shortest[now] < di ) continue;
        // 현재 지점에 연결된 곳 차례로 방문. 
        for(int i=0; i<city[now].size(); i++){
            int next = city[now][i].first;
            int nextDist = city[now][i].second+di;
            
            // 출발지점->now->next 경유하는 도로가 알고있는 최단경로보다 짧은 경우 갱신. 
            if( shortest[next] >= nextDist ){
                shortest[next] = nextDist;
                pq.push(make_pair(-nextDist, next));
            }
        }
    }
    // start에서 다른 모든 정점으로의 최단거리를 담은 벡터를 리턴. 
    return shortest;
}
 
int main(){
    scanf("%d", &T);        // 테스트케이스 입력
    for(int i=0; i<T; i++){
         /*init*/
         for(int i=0; i<2001; i++){
             city[i].clear();
        }
        dest.clear(); 
        /*input*/
        scanf("%d %d %d", &n, &m, &t);
        scanf("%d %d %d", &s, &g, &h);
        // m개의 도로 입력. 
        for(int i=0; i<m; i++){
            int start, end, dist;
            scanf("%d %d %d", &start, &end, &dist);
            city[start].push_back(make_pair(end, dist));
            city[end].push_back(make_pair(start, dist));
        }
        // t개의 목적지 후보 입력. 
        for(int i=0; i<t; i++){
            int x;
            scanf("%d", &x);
            dest.push_back(x);
        }
        // 목적지 후보들을 오름차순으로 정렬
        sort(dest.begin(), dest.end());
        
        /*solve*/
        vector<int> sS = dijkstra(s);
        vector<int> sG = dijkstra(g);
        vector<int> sH = dijkstra(h);
        
        // 시작~목적지 후보까지의 최단거리가 s-g-h-t 또는 s-h-g-t라면
// 경유지를 모두 지났으므로 출력한다.
        for(int i=0; i<dest.size(); i++){
            int sght = sG[s]+sG[h]+sH[dest[i]];
            int shgt = sH[s]+sH[g]+sG[dest[i]];
            int st = sS[dest[i]];
            if( st==sght || st==shgt ){
                printf("%d ", dest[i]);
            }
        }
        printf("\n");
    } 
    return 0;
}
 cs

2.

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 <cstdio> 
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int T;
int n, m, t;
int s, g, h;
int INF = 2000000000;
vector< pair<int, int> > city[2001];    // 인덱스 1~n을 사용한다. 
vector<int> dest;    //목적지 후보 저장
 
vector<int> dijkstra(int start){
    vector<int> shortest(n+1, INF);        // 인덱스 1~n을 사용. 
    shortest[start] = 0;
    priority_queue< pair<int, int> > pq;
    pq.push(make_pair(0, start));
    
    while(!pq.empty()){
        int now = pq.top().second;
        int nowcost = -pq.top().first;
        pq.pop();
        
        for(int i=0; i<city[now].size(); i++){
            int next = city[now][i].first;
            int nextcost = nowcost + city[now][i].second;
            if( shortest[next] > nextcost ){
                shortest[next] = nextcost;
                pq.push(make_pair(-nextcost, next));
            }
        }
    }
    return shortest;
}
 
int main(){
    cin>>T;
    for(int i=0; i<T; i++){
        /*init & input*/
        for(int i=0; i<2001; i++)
            city[i].clear();
        dest.clear();
        cin>>n>>m>>t;
        cin>>s>>g>>h;
        for(int i=0; i<m; i++){
            int a, b, d;
            cin>>a>>b>>d;
            city[a].push_back(make_pair(b, d));
            city[b].push_back(make_pair(a, d));
        }
        for(int i=0; i<t; i++){
            int x;
            cin>>x;
            dest.push_back(x);
        }
        
        /*solve*/
        // 목적지 후보들을 오름차순 정렬한다. 
        sort(dest.begin(), dest.end());
        vector<int> startG = dijkstra(g);
        vector<int> startH = dijkstra(h);
        vector<int> startS = dijkstra(s);
        
        int sgh = startG[s]+startG[h];
        int shg = startH[s]+startG[h];
        for(int i=0; i<dest.size(); i++){
            int cur = dest[i];
            int sght = sgh+startH[cur];
            int shgt = shg+startG[cur];
            int st = startS[cur];
            if( sght==st){
                printf("%d ", cur);
            }
            else if (shgt==st){
                printf("%d ", cur);
            }
        }
        printf("\n");
    }
} 
 cs

 

##

틀렸다는 판정을 계속 받아서 코드를 새로 작성하고, 다른 사람들의 코드와도 비교해가며 해답을 찾았다.

처음 코드에서 틀렸던 점은, dijkstra(int start) 함수 내부의 shortest배열의 start인덱스 위치 값을 0으로 초기화해주지 않아서 최단경로를 찾지 못했던 것이었다.

두 번째 코드에서 틀렸던 점은 처음 코드의 틀린 점은 보완했지만, shortest 벡터의 인덱스를 1~n까지 사용하면서 0~n-1만큼만 INF로 초기화해서 문제가 발생했다.

각각의 소스 코드에서 빠트렸던 부분은 굵게 표시해뒀으니 꼭 다시 읽고 같은 실수 반복하지 않도록 하자.

초기 코드 형태에서 완전히 수정한 것

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
#include <iostream>
#include <cstdio> 
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
int INF = 2000000000;
int T;                // 테스트케이스개수 
int n, m, t;        // 도시개수, 도로개수, 목적지후보개수 
int s, g, h;        // 출발지, 경유지1, 경유지2 
vector<pair<int, int> > city[2001];        // 도시 간 연결 저장 
vector<int> dest;                        // 목적지 후보들 저장
 
vector<int> dijkstra(int start){
    priority_queue<pair<int, int> > pq;
    // -거리, 도시번호, 두 경유지 경유 여부 저장.
    vector<int> shortest(n+1, INF);
    // 출발-출발거리 :0, 출발지점, 경유지 사이 도로 지났는지 큐에 push 
    pq.push(make_pair(0, start));
    shortest[start] = 0;
    
    while(!pq.empty()){
        int now = pq.top().second;
        int di = -pq.top().first;
        pq.pop();
        
        if( shortest[now] < di ) continue;
        // 현재 지점에 연결된 곳 차례로 방문. 
        for(int i=0; i<city[now].size(); i++){
            int next = city[now][i].first;
            int nextDist = city[now][i].second+di;
            
            // 출발지점->now->next 경유하는 도로가 알고있는 최단경로보다 짧은 경우 갱신. 
            if( shortest[next] >= nextDist ){
                shortest[next] = nextDist;
                pq.push(make_pair(-nextDist, next));
            }
        }
    }
    // start에서 다른 모든 정점으로의 최단거리를 담은 벡터를 리턴. 
    return shortest;
}
void input(){
    /*init*/
     for(int i=0; i<2001; i++){
         city[i].clear();
    }
    dest.clear(); 
    /*input*/
    scanf("%d %d %d", &n, &m, &t);
    scanf("%d %d %d", &s, &g, &h);
    // m개의 도로 입력. 
    for(int i=0; i<m; i++){
        int start, end, dist;
        scanf("%d %d %d", &start, &end, &dist);
        city[start].push_back(make_pair(end, dist));
        city[end].push_back(make_pair(start, dist));
    }
    // t개의 목적지 후보 입력. 
    for(int i=0; i<t; i++){
        int x;
        scanf("%d", &x);
        dest.push_back(x);
    }
    // 목적지 후보들을 오름차순으로 정렬
    sort(dest.begin(), dest.end());
}
void solve(){
    vector<int> sS = dijkstra(s);
    vector<int> sG = dijkstra(g);
    vector<int> sH = dijkstra(h);
    
    // 시작~목적지 후보까지의 최단거리가 s-g-h-t 또는 s-h-g-t라면 경유지를 모두 지났으므로 출력한다. 
    for(int i=0; i<dest.size(); i++){
        int sght = sG[s]+sG[h]+sH[dest[i]];
        int shgt = sH[s]+sH[g]+sG[dest[i]];
        int st = sS[dest[i]];
        if( st==sght || st==shgt ){
            printf("%d ", dest[i]);
        }
    }
    printf("\n");
}
 
int main(){
    scanf("%d", &T);        // 테스트케이스 입력
    for(int i=0; i<T; i++){
         input();
         solve();
    } 
    return 0;
}
cs

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 11047번 :: 동전 0  (0) 2019.12.15
BOJ 12865번 :: 평범한 배낭  (0) 2019.12.14
BOJ 1912번 :: 연속합  (0) 2019.12.09
BOJ 9251번 :: LCS  (0) 2019.12.09
BOJ 1504번 :: 특정한 최단 경로  (0) 2019.12.08

#문제

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

 

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
#include <vector>
using namespace std;
 
const int MAX = 100000;
int n;
int sum[MAX];
int serial[MAX];
 
void input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>serial[i];
    }
}
 
int solve(){
    // 첫 번째 원소로 가장 큰 연속합, 첫 번째 연속합 초기화. 
    int sumMax=serial[0];
    sum[0] = serial[0];
    for(int i=1; i<n; i++){
        // '현재 원소 < 이전 연속합 + 현재원소' 일 때 더 큰 것을 sum[i]로 저장. 
        sum[i] = max(sum[i-1]+serial[i], serial[i]);
        // 가장 큰 연속합을 갱신한다. 
        sumMax = max(sumMax, sum[i]);
    }
    return sumMax;
}
 
int main(){
    input();
    cout<<solve();
    return 0;
}
 cs

##

처음에 2차원 DP를 사용해서 풀려고 코드를 작성했는데,

int sum[100000][100000]; 으로 sum 배열을 선언하고 컴파일하니 컴파일 에러가 발생했다.

구글링해보니, 4*10^10Byte -> 4GB라서 배열의 사이즈가 너무 커서 문제가 생긴것이었다.

 

저작자표시

'BOJ' 카테고리의 다른 글

BOJ 12865번 :: 평범한 배낭  (0) 2019.12.14
BOJ 9370번 :: 미확인 도착지  (0) 2019.12.13
BOJ 9251번 :: LCS  (0) 2019.12.09
BOJ 1504번 :: 특정한 최단 경로  (0) 2019.12.08
BOJ 2206번 :: 벽 부수고 이동하기  (0) 2019.12.08

#문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

#작성 코드

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
#include <iostream>
#include <string>
using namespace std;
 
#define MAX 1000
string stra, strb;
int c[MAX+1][MAX+1];        // 0으로 채워진 행과 열을 앞에 추가. 
 
void input(){
    cin>>stra;
    cin>>strb;
}
 
int findLCS(string stra, string strb){
    // stra와 strb의 문자열을 하나하나 비교. 
    for(int i=1; i<=stra.length(); i++){
        for(int j=1; j<=strb.length(); j++){
            // 현재 비교하는 문자열이 같지 않으면
            // 이 위치 전까지 존재하는 lCS 중 가장 긴 수를 유지한다. 
            if( stra[i-1]!=strb[j-1] ){
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
            else{
                // stra[i-1]==strb[j-1]
                // stra, strb 각각 한 문자열 전까지 lCS길이에 1을 추가한다. 
                c[i][j] = c[i-1][j-1]+1; 
            }
        }
    }
    return c[stra.length()][strb.length()];
}
 
int main(){
    input();
    cout<<findLCS(stra, strb);
    return 0;    
}
 cs

##

어제 유튜브에서 봤던 minumum edit distance 문제와 비슷했다. https://youtu.be/b6AGUjqIPsA

저작자표시

'BOJ' 카테고리의 다른 글

BOJ 9370번 :: 미확인 도착지  (0) 2019.12.13
BOJ 1912번 :: 연속합  (0) 2019.12.09
BOJ 1504번 :: 특정한 최단 경로  (0) 2019.12.08
BOJ 2206번 :: 벽 부수고 이동하기  (0) 2019.12.08
BOJ 1697번 :: 숨바꼭질  (0) 2019.12.08

#문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

#작성 코드

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
 
void input(){
    //  정점의 개수, 간선의 개수 입력 
    scanf("%d %d", &N, &E);
    // 그래프 입력 
    for(int i=0; i<E; i++){
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        // 양방향 그래프! 
        node[start].push_back(make_pair(end, cost));
        node[end].push_back(make_pair(start, cost));
    }
    // 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 
    scanf("%d %d", &one, &two);
}
 
int dijkstra(int start, int end){
    // start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화. 
    long long int shortest[801];
    fill_n(shortest, 801, INF);
    
    priority_queue< pair<int, int> > pq;
    // 우선순위 큐에 시작 정점 push.  
    pq.push(make_pair(0, start));
    shortest[start] = 0; 
    
    while(!pq.empty()){
        // 현재 위치의 정점에 대해 탐색. 
        int now = pq.top().second;
        int nowcost = -pq.top().first;
        pq.pop();
        // 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스 
        if( shortest[now] < nowcost ) continue;
        
        // now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체. 
        for( int i=0; i<node[now].size(); i++){
            int next = node[now][i].first;
            int nextcost = node[now][i].second + nowcost;
            
            if( shortest[next] > nextcost ){
                shortest[next] = nextcost;
                pq.push(make_pair(-nextcost, next));
                // 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다. 
            }
        }
    }
 
    // end까지의 최단거리 갱신이 안되었다면 -1을 리턴한다. 
    if( shortest[end] >= INF ) return -1;
    // end까지의 최단거리가 존재한다면 그 거리를 리턴 
    else    return shortest[end];
}
 
int solve(){
    int startToOne = dijkstra(1, one);
    int startToTwo = dijkstra(1, two);
    int oneToTwo = dijkstra(one, two);
    int twoToEnd = dijkstra(two, N);
    int oneToEnd = dijkstra(one, N);
    int result1=0, result2=0;
    bool flag1 = true, flag2 = true;
    // 경로 중 하나라도 최단거리를 찾지 못하는 경로가 있다면 -1을 출력한다. 
    // 경로 1번 : 1->one->two->N
    if( startToOne==-1 || oneToTwo==-1 || twoToEnd==-1 ){
        flag1 = false;
    }
    // 경로 2번 : 1->two->one->N
    if( startToTwo==-1 || oneToTwo==-1 || oneToEnd==-1 ){
        flag2 = false;
    }
 
    result1 = startToOne+oneToTwo+twoToEnd;        // 경로1번 결과 
    result2 = startToTwo+oneToTwo+oneToEnd;        // 경로2번 결과 
 
    // 경로 1번, 경로 2번 모두 불가능 할 때 
    if( !flag1 && !flag2 ){
        return -1; 
    }
    // 경로 1만 가능할때 
    else if( flag1 && !flag2 ){
        return result1;
    }
    // 경로 2만 가능할때 
    else if( flag2 && !flag1){
        return result2;
    }
    // 경로 1과 2 모두 가능할 때 
    else{
        return min(result1, result2);
    }
}
int main(){
    input();
    printf("%d\n", solve());
    return 0;
}
 cs

##

정점의 개수 N이 최대 800개 가능하므로 vector< pair<int, int> > node[801];을 생성한다.

a번 정점에서 b번 정점까지 거리가 c인 양방향 길이 존재 -> node[a]에 {b, c}를 push, node[b]에 {a, c}를 push 한다.

반드시 거쳐야 하는 두 개의 서로 다른 정점을 입력받고 one, two라는 전역변수에 저장한다.

 

맞는 것 같은데, 계속해서 틀렸습니다 판정을 받아서 반례를 게시판에서 찾아 체크했는데 모두 알맞게 나왔다.

문제는, line 90, 94에서 flag1과 flag2에 대해서만 검사하고 !flag2, !flag1 검사를 해주지 않았기 때문에 발생했다.

조건에 대해서는 하나하나 꼭 체크 해주자!!

 

 

#191209 REVIEW

1. line 72~100에서 flag1과 flag2를 체크하는 방법 이외에,

dijkstra()함수에서 INF보다 큰 경우에 -1을 리턴하는 대신 INF 값 그대로를 리턴하게 하고,

result = min(result1, result2) 를 저장해놓고,

result>=INF 라면 -1을 출력하고, 아니라면 result를 출력하게 하는 방법으로 하면 좀 더 간단하게 처리할 수 있겠다.

 

2. dijkstra 함수의 리턴형을 vector<int>로 교체.

startToOne, startToTwo는 원래 코드에서, 같은 결과의 shortest[]배열을 생성하고, 배열 내에서 리턴하는 값의 위치만 달랐다.

dijkstra함수를 start에서 시작해서 다른 모든 정점으로의 최단거리를 계산한 vector를 리턴하도록 해서,

startToOne, startToTwo를 동일한 결과값에서 추출할 수 있도록 변경했다.

더보기
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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
 
int N, E;
int one, two;
vector< pair<int, int> > node[801];
int INF = 800001;
 
void input(){
    //  정점의 개수, 간선의 개수 입력 
    scanf("%d %d", &N, &E);
    // 그래프 입력 
    for(int i=0; i<E; i++){
        int start, end, cost;
        scanf("%d %d %d", &start, &end, &cost);
        // 양방향 그래프! 
        node[start].push_back(make_pair(end, cost));
        node[end].push_back(make_pair(start, cost));
    }
    // 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 
    scanf("%d %d", &one, &two);
}
 
vector<int> dijkstra(int start){
    // start 에서 시작해서 각 정점으로 가는 최단거리 무한대로 초기화. 
// vector를 리턴하도록 수정해보았다. 
    vector<int> shortest(801, INF);
    
    priority_queue< pair<int, int> > pq;
    // 우선순위 큐에 시작 정점 push.  
    pq.push(make_pair(0, start));
    shortest[start] = 0; 
    
    while(!pq.empty()){
        // 현재 위치의 정점에 대해 탐색. 
        int now = pq.top().second;
        int nowcost = -pq.top().first;
        pq.pop();
        // 알고 있는 start->now 최단거리보다 nowcost가 크면 이 정점은 패스 
        if( shortest[now] < nowcost ) continue;
        
        // now를 경유해서 갈 수 있는 정점에 경유해서 가는 거리가 더 짧다면 교체. 
        for( int i=0; i<node[now].size(); i++){
            int next = node[now][i].first;
            int nextcost = node[now][i].second + nowcost;
            
            if( shortest[next] > nextcost ){
                shortest[next] = nextcost;
                pq.push(make_pair(-nextcost, next));
                // 우선순위 큐를 사용하므로 cost를 음수화해서 저장해야 작은것부터 꺼낼 수 있다. 
            }
        }
    }
// start부터 다른 모든 정점으로의 최단거리를 저장한 벡터자체를 리턴함. 
    return shortest;
}
 
int solve(){
    vector<int> sStart = dijkstra(1);
    int startToOne = sStart[one];
    int startToTwo = sStart[two];
    
    vector<int> sOne = dijkstra(one);
    int oneToTwo = sOne[two];
    // one->two와 two->one은 동일하므로 한번만 사용. 
    
    vector<int> sEnd = dijkstra(N);
    int twoToEnd = sEnd[two];
    int oneToEnd = sEnd[one];
 
    // 두 가지 경로의 결과값 저장. 
    int result1=0, result2=0;    
    result1 = startToOne+oneToTwo+twoToEnd;        // 경로1번 결과 
    result2 = startToTwo+oneToTwo+oneToEnd;        // 경로2번 결과 
    
//수정한 부분! 
    int result = min(result1, result2);
    if( result>=INF )    return -1;
    else return result;
}
 
int main(){
    input();
    printf("%d\n", solve());
    return 0;
}
 cs

'BOJ' 카테고리의 다른 글

BOJ 1912번 :: 연속합  (0) 2019.12.09
BOJ 9251번 :: LCS  (0) 2019.12.09
BOJ 2206번 :: 벽 부수고 이동하기  (0) 2019.12.08
BOJ 1697번 :: 숨바꼭질  (0) 2019.12.08
BOJ 2565번 :: 전깃줄  (0) 2019.12.07

# 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

#작성 코드

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 <cstdio>
#include <queue>
using namespace std;
 
#define MAX 1001
 
int N, M;
int map[MAX][MAX];            // 인덱스 1~1000을 사용한다. 
int visit[MAX][MAX][2];
// [][][0]은 벽을 부수지 않고 이동한 경로
// [][][1]은 벽을 부수고 이동한 경로
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};    // 상하좌우 탐색에 사용 
 
void input(){
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            scanf("%1d", &map[i][j]);
        }
    }
} 
 
// 맵 범위 내에 좌표 존재 여부 리턴. 
bool isIn(int x, int y){
    return x>=1&&x<=N&&y>=1&&y<=M;
}
 
int solve(){
    queue< pair<pair<int, int>, bool> > q;
    // x좌표, y좌표, 벽 부순 여부
    
    q.push(make_pair(make_pair(1, 1), 0));
    visit[1][1][0] = 1; 
    
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        bool z = q.front().second;
        q.pop();
        // 이번에 큐에서 꺼낸 위치가 도착 위치라면 리턴!
        if( x==N && y==M ) return visit[x][y][z]; 
        
        for(int i=0; i<4; i++){
            int nx = x+d[i][0];
            int ny = y+d[i][1];
            
            if( isIn(nx, ny)&&map[nx][ny]==0&&visit[nx][ny][z]==0){
                // 새 위치가 길이고
                // 이 위치에 방문한 적 없다면 
                // 전에 벽 부순 여부에 상관없이
                // 그 상태를 유지하며 방문표시! 
                visit[nx][ny][z] = visit[x][y][z]+1;
                q.push(make_pair(make_pair(nx, ny),z));
            }
            if( isIn(nx, ny)&&z==0&&map[nx][ny]==1&&visit[nx][ny][1]==0){
                // 벽을 부순적 없고,
                // 새 위치가 벽이며,
                // 이 벽을 아직 부수고 방문한 적 없을 때 
                visit[nx][ny][1] = visit[x][y][0]+1;
                q.push(make_pair(make_pair(nx, ny),1));
                    // 앞으로는 벽을 부순 경로만 탐색할것임! 
            }
        }
    }
    return -1;
}
 
int main(){
    input();
    cout<<solve();
    return 0;
}
 cs

##

queue에 { {x좌표, y좌표}, 벽 부순 여부 } 를 push하면서 탐색했다.

이전에 벽을 부쉈는지, 벽을 부수지 않았는지에 따라 이후에 탐색하는 경로가 달라진다.

#191209 REVIEW code update

'BOJ' 카테고리의 다른 글

BOJ 9251번 :: LCS  (0) 2019.12.09
BOJ 1504번 :: 특정한 최단 경로  (0) 2019.12.08
BOJ 1697번 :: 숨바꼭질  (0) 2019.12.08
BOJ 2565번 :: 전깃줄  (0) 2019.12.07
BOJ 9012번 :: 괄호  (0) 2019.12.06

+ Recent posts

티스토리툴바