다익스트라4 [BOJ/PYTHON] 2423. 전구를 켜라 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/2423 문제 요약 N × M 직사각형 크기의 전자 회로에서 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜짐 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값 구하기 핵심 아이디어 불가능할 경우 "NO SOLUTION”을 출력해야 하는데, N + M이 홀수인 경우 물리적으로 불을 켜는 것이 불가능하다. 다익스트라로 푼다고 가정했을 때 비용값을 구하는 것이 필요한데, ‘돌려야 하는 칸의 개수의 최솟값’을 구해야 하기 때문에 돌릴 필요가 없으면 0, 돌려야 하면 1로 비용을 산정하면 된다. “/”일 때는 (i, j+1)에서 (i+1, j) 방향으.. 2023. 5. 18. [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] 18223. 민준이와 마산 그리고 건우 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/18223 문제 요약 마산(도착지, v번 정점)이 더 가까우면 그냥 마산으로, 최단 경로에 건우가 있으면 겸사겸사 구해줌 민준이가 찾은 최단 경로 위에 건우가 있다면 "SAVE HIM" 을 아니면 "GOOD BYE" 를 출력 핵심 아이디어 그래프 간선에 가중치가 있고, 가중치가 양수이기 때문에 다익스트라 알고리즘을 사용하면 된다. 이때, 건우를 구해준 후 마저 마산까지 가는 거리가 최단경로보다 길어지지 않으면 건우를 구하는 거라 건우를 구하러까지 가는 최단 거리, 구하고 나서 마산까지 가는 최단 거리, 출발지에서 마산까지 직통으로 가는 최단 거리값들이 필요하다. 풀이 # gold4-18223. 민준이와 마산 그리고 건우 impor.. 2023. 5. 16. 이전 1 다음