다익스트라6 [알고리즘] 특정한 최단 경로 (백준 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. [알고리즘] 알고스팟 (백준 1261번) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 처음엔 이분탐색을 이용해야하는 줄 알았는데 시간 초과, 메모리 초과가 났다. 이후에 BFS로 풀었는데 원래는 다익스트라 문제다. 결론적으로 다익스트라가 시간, 메모리가 더 적게 걸린다. Solution 1. BFS 버전 import java.io.BufferedReader import java.io.BufferedWriter import java.io.InputStreamReader import java.io.OutputStreamWrite.. 2020. 10. 6. 이전 1 2 다음
