Algorithm/Graph188 [파이썬] 백준 11779 : 최소비용 구하기 2 (골드3) [파이썬] 백준 11779 : 최소비용 구하기 2 (골드3)https://www.acmicpc.net/problem/11779풀이방향성 생각최소비용 구하기 1916 이랑 같은 문제.다익스트라 + 역추적기존 다익스트라 배열에 previous node를 기록해주는 리스트를 추가한다.전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())M = int(input())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))start,end = map(int,in.. 2024. 11. 21. [파이썬] 백준 1916 : 최소비용 구하기 (골드5) [파이썬] 백준 1916 : 최소비용 구하기 (골드5)https://www.acmicpc.net/problem/1916풀이방향성 생각전형적인 다익 기본A -> B로가는 최소 거리전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N = int(input())M = int(input())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))start,end = map(int,input().split())V = [float('inf')]*(N+1)V[start] = 0heap = .. 2024. 11. 21. [파이썬] 백준 1753 : 최단경로 (골드4) [파이썬] 백준 1753 : 최단경로 (골드4)https://www.acmicpc.net/problem/1753풀이방향성 생각방향 그래프의 node A에서 다른 노드까지의 거리를 구하는 문제입력 크기를 보면 node = 20000에 edges = 300000이라 다익스트라로 풀이.주의할점은 node간 중복 간선이 주어져서 처리를 해야한다.defaultdict로 이중 딕셔너리 만들어서 최솟값으로 갱신하는 방식으로 풀이전체코드from collections import defaultdict as ddimport heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()N,K = map(int,input().split())start = int(in.. 2024. 11. 18. [파이썬] 백준 2479 : 경로찾기 (골드4) [파이썬] 백준 2479 : 경로찾기 (골드4)https://www.acmicpc.net/problem/2479풀이방향성 생각binary로 들어오는 데이터들을 정수형으로 변환한다.key index 정수 변환에 필요한 두 딕셔너리를 만든다.들어오는 bit 수가 1000개여서 전부 관리 가능하다.bit 연산을 통해서 입력 정수에 대해서 그래프를 만들어준다.BFS를 통해서 탐색하기단수 T/F 연산이 아니라 역추적이 필요하기 때문에 어디서 왔는지 기록목적지에 도달했으면 역추적, 아니면 -1 출력전체코드from collections import deque ,defaultdict as ddN,K = map(int,input().split())# key index bitnum_bin = {i:int(input().. 2024. 11. 16. 이전 1 ··· 17 18 19 20 21 22 23 ··· 47 다음