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!

인기 글

태그

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

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Henu

개발냥발

[백준 17182] 우주 탐사선 (C++)
Algorithm/BOJ

[백준 17182] 우주 탐사선 (C++)

2021. 8. 4. 14:21
 

17182번: 우주 탐사선

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위

www.acmicpc.net

다익스트라, 다이나믹 프로그래밍, 비트마스킹


 

 

[백준 13308] 주유소 (C++)

13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리

hyeo-noo.tistory.com

얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다

 

모든 행성이 서로 이어져 있고, 모든 행성을 방문해야하며, 행성을 중복해서 방문할 수 있다고 주어졌다.

 

행성을 중복해서 방문할 수 있다는 점과 N이 최대 10인 점을 보니 예전에 풀었던 비트필드를 통해서 방문여부를 체크해주는 외판원 문제가 생각이났다.

 

이 문제도 마찬가지로 2차원 dp배열을 사용하면서 방문기록이 같은데 이미 방문한 정점을 다시 방문하는 경우 건너뛰는 방법을 사용해서 중복탐색을 없앴다.

dp[현재행성][방문기록] = -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
#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;
 
struct P{
    int planet;
    int visited;
    int cost;
};
 
struct cmp{
    bool operator()(P &a, P &b){
        return a.cost > b.cost;
    }
};
 
int N, K, check;
int Cost[11][11];
// 현재 정점, 지금까지 지나온 경로
int dp[11][1 << 10];
 
void input(){
    cin >> N >> K;
    int a;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Cost[i][j];
        }
    }
    check = (1 << N) - 1;
    memset(dp, -1, sizeof(dp));
}
 
void solve(){
    priority_queue<P, vector<P>, cmp> pq;
    pq.push({K, (1 << K), 0});
    
    
    while(!pq.empty()){
        int now = pq.top().planet;
        int now_cost = pq.top().cost;
        int visit = pq.top().visited;
        pq.pop();
        
        if(dp[now][visit] != -1) continue;
        dp[now][visit] = now_cost;
        
        if(visit == check){
            cout << now_cost << "\n";
            return;
        }
        
        for(int next = 0; next < N; next++){
            if(next == now) continue;
            int next_cost = now_cost + Cost[now][next];
            int visited = visit | (1 << next);
            
            if(dp[next][visited] != -1) continue;
            pq.push({next, visited, next_cost});
        }
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}
 
Colored by Color Scripter
cs

 

'Algorithm > BOJ' 카테고리의 다른 글

[백준 5527] 전구 장식 (C++)  (0) 2021.08.06
[백준 17142] 연구소 3 (C++)  (0) 2021.08.04
[백준 2026] 소풍 (C++)  (0) 2021.08.04
[백준 14284] 간선 이어가기 2 (C++)  (0) 2021.08.04
[백준 14391] 종이 조각 (C++)  (2) 2021.08.04
    'Algorithm/BOJ' 카테고리의 다른 글
    • [백준 5527] 전구 장식 (C++)
    • [백준 17142] 연구소 3 (C++)
    • [백준 2026] 소풍 (C++)
    • [백준 14284] 간선 이어가기 2 (C++)

    티스토리툴바