백준34 [BOJ/PYTHON] 9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/9694 문제 요약 최고의원을 만나기까지의 친밀도의 합 중에서 가장 작은 값을 구하기 친밀도: (최측근 [1] / 측근 [2] / 비즈니스관계 [3] / 지인 [4]) 최고의원을 만날수 있다면 0번 정치인(한신이)를 시작으로 M-1번 정치인(최고의원)까지 만난 순서대로 출력, 최고의원을 만날수 없는 경우엔 -1을 출력 핵심 아이디어 ‘관계’가 사람과 사람 간 관계라는 것을 고려했을 때, 사람(정치인)은 정점, 관계는 간선으로 보면 된다. 친밀도의 정도가 정해져있으므로 친밀도를 거리 값으로 간주, 다익스트라 알고리즘으로 풀면 된다. 풀이 # gold3-9694. 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 import sys, h.. 2023. 5. 16. [BOJ/PYTHON] 11779. 최소비용 구하기 2 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/11779 문제 요약 A번째 도시에서 B번째 도시로 가는 최소비용과 경로 구하기 핵심 아이디어 문제를 읽으며 도시가 정점, 버스가 간선, 버스 비용은 가중치라는 것을 파악하면 된다! 비용이 양수라 다익스트라로 풀면 된다. ‘경로’ 구하는 게 필요했는데, 애초에 최단거리 갱신할 때 경로 정보도 같이 넣어주면 된다. 다익스트라 함수를 돌리며 현재 보는 노드가 ‘도착 도시’일 때 해당 값을 출력하면 된다. 풀이 # gold3-11779. 최소비용 구하기 2 import sys, heapq input = sys.stdin.readline n = int(input()) # 도시의 개수 m = int(input()) # 버스의 개수 grap.. 2023. 5. 16. [BOJ/PYTHON] 11657. 타임머신 (최단 경로 - 벨만포드) 백준 문제 링크: https://www.acmicpc.net/problem/11657 문제 요약 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하기 이동시간이 양수면 그만큼 이동, 0이면 순간이동, 음수면 타임머신으로 시간 되돌아감 핵심 아이디어 시작점, 도착점, 시간이 주어졌기에 정점과 간선의 가중치가 주어진 상황이다. 근데 이 시간이 음수 값도 가능하기에 다익스트라로 풀 수 없다. 벨만포드로 풀면 된다. 풀이 # gold4-11657. 타임머신 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 도시 개수, 버스 노선 개수 edges = [] for _ in range(m): a, b, c = map(int.. 2023. 5. 16. [BOJ/PYTHON] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/18223 문제 요약 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력 핵심 아이디어 그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다. 이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다. 풀이 # gold4-18223. 민준이와 마산 그리고 건우 impor.. 2023. 5. 16. 이전 1 ··· 3 4 5 6 다음