그래프16 [알고리즘] 특정한 최단 경로 (백준 1504번) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 그래프 이론 문제로 1번 노드에서 N번 노드까지의 최단 거리를 구해야 하는데 중간에 V1, V2에 해당하는 노드들을 꼭 거쳐가야 한다. Solution 우선 문제에서 유추할 수 있는 것을 찾아본다면 가중 그래프에서의 최단 경로 다익스트라, 플로이드 와샬 예상 무향 그래프 위상 정렬은 사용 불가 (사이클 o) v1, v2를 무조건 거쳐야 함 (나올 수 있는 최단 경로의 수는 2개) 1 → v1 → v2 → N 1 → v.. 2020. 11. 11. [알고리즘] 파티 (백준 1238번) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 최단 시간만에 X번까지 왕복하는 시간을 구해야한다. 즉 각 마을에서 X번까지의 최단 시간, X번에서 각 마을까지의 최단 시간을 둘 다 구해야한다. 가장 쉽게 생각할 수 있는 방법은 플로이드 와샬로 모든 구간의 최단 시간을 구하는 것이다. 시간이 오래 걸리지만 풀긴 풀 수 있는 것 같다. (사실 1000의 3제곱이면 10억인데 못 풀 거라 생각했는데 풀긴 풀더라...) 하지만 X번까지의 왕복 정보 외에는 다른 정보들은 필요가 없다... 2020. 10. 7. [알고리즘] 숨바꼭질 3 (백준 13549번) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 처음엔 BFS인 줄 알았는데 자세히 보니 이동하는 위치에 따라서 이동시간이 다르다. 이 말은 곧 간선마다의 가중치가 다르다는 뜻이므로 다익스트라를 이용해야 한다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java... 2020. 10. 7. [알고리즘] ABCDE (백준 13023번) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 형태를 보면 알겠지만 DFS를 활용해서 depth를 파악해야하는 문제다. 처음엔 모든 노드들을 각각 시작점으로 하여서 한 번씩 DFS를 돌리려고 했는데 어째서인지 틀렸다고 나왔다. Solution import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWriter import java.util.* import kotlin.collections.ArrayList var br = BufferedReader(In.. 2020. 10. 6. 이전 1 2 3 4 다음
