본문 바로가기

Problem Solving

 (135)
[ BOJ 백준 11657번 - 타임머신 ] 해설 및 코드 https://www.acmicpc.net/problem/11657 목적 음의 가중치가 존재하는 방향 그래프에서 최단 거리를 구하고 음의 사이클이 존재하는지 확인하자. 접근법 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 #include #define f(i,l,r) for(int i=l;i>n>>m; f(i,1,m){ int a,b,c;cin>>a>>b>>c; edge[i][0]=a; edge[i][1]=b; edge[i][2]=c; } dist[1]=0;f(i,2,n)dist[i]=I..
[ BOJ 백준 10159번 - 저울 ] 해설 및 코드 https://www.acmicpc.net/problem/10159 목적 물건 쌍의 비교 결과를 알 수 있는지 구하자. 접근법 1. 플로이드 와샬 알고리즘을 이용하여 방향 그래프의 연결 여부를 구한다. 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 #include #define f(i,l,r) for(int i=l;i>n>>m; f(i,1,n)g[i][i]=1; while(m--){ int a,b;cin>>a>>b; g[a][b]=1; } f(k,1,n)f(i,1,n)f(j,1,n)if(g[i][k]&&g[k][j])g[i][j]=1; f(i,1,n){ int cnt=n; ..
[ BOJ 백준 11404번 - 플로이드 ] 해설 및 코드 https://www.acmicpc.net/problem/11404 목적 모든 정점간 최단 거리를 구하자. 접근법 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 #include #define f(i,r,l) for(int i=r;i> n >> m; f(i, 1, n) { f(j, 1, n)s[i][j] = INF; s[i][i] = 0; } while (m--) { int a, b, c; cin >> a >> b >> c; s[a][b] = min(s[a][b], c); } f(k, 1, n)f(i, 1, n)f(j..
[ BOJ 백준 1389번 - 케빈 베이컨의 6단계 법칙 ] 해설 및 코드 https://www.acmicpc.net/problem/1389 목적 각 정점간의 거리를 구하고, i정점에서 나머지 정점간 거리의 합이 최소인 i를 구하자. 접근법 1. 플로이드 와샬 알고리즘을 이용해 모든 정점간 거리를 구하자. 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 #include #define f(i,r,l) for(int i=r;i> n>>m; f(i, 1, n) { f(j, 1, n)s[i][j] = INF; s[i][i] = 0; } while (m--) { int a, b; cin >> a >> b; s[a][b] ..
[ BOJ 백준 2211번 - 네트워크 복구 ] 해설 및 코드 https://www.acmicpc.net/problem/2211 목적 본문을 요약하자면 최소 스패닝 트리를 구하라는 것이다. 접근법 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 #include #define f(i,r,l) for(int i=r;i tmp) { a[i] = tmp; b[i] = v; q.push({ tmp,i }); } } } cout
[ BOJ 백준 5719번 - 거의 최단 경로 ] 해설 및 코드 https://www.acmicpc.net/problem/5719 목적 최단 경로를 모두 제거한 뒤에 최단 경로를 구하자. 접근법 1. 다익스트라 알고리즘으로 S에서 D로 가는 최단 경로를 구하자. 2. 그런다음 여러개가 될 수 있는 최단경로를 백트래킹으로 D부터 S까지 지워준다. 3. 이제 다시 최단 경로를 구하면 원하는 답이 나온다. 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 #include #define f(i,r,l) for(int i=r;i tmp) {..
[ BOJ 백준 1916번 - 최소비용 구하기 ] 해설 및 코드 https://www.acmicpc.net/problem/1916 목적 두 정점간의 최단 거리를 구하자. 접근법 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 #include #include #include #define MAX_N 1001 #define MAX_W (int)1e10 using namespace std; struct info { int v, w; bool operator oth.w; } }; void go(int n,..
[ BOJ 백준 1753번 - 최단경로 ] 해설 및 코드 https://www.acmicpc.net/problem/1753 목적 방향그래프에서 최단경로를 구하자. 접근법 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 #include #include #include #define MAX_V 20001 #define MAX_W 200001 using namespace std; struct info { int u, w; bool operator oth.w; } }; void go(int V, int K, vector* G) { vector sp..

티스토리툴바