[BOJ] [Python] 1753번 : 최단경로
처음에는 2차원 배열을 이용해서 푸려는 무모한 계획을 세웠다. 이 문제에서 2차원 배열을 이용하려면, 최대 20000 x 20000[400,000,000]이 필요하다. 파이썬은 300,000,000부터 메모리 초과가 난다. 100,000,000에 381MB이다. 이 문제는 메모리가 256MB 제한이라서 300,000,000보다 작아도 메모리 초과이다. 그래서 2차원 배열 대신 heapq를 이용하여 풀었다. heapq를 사용한 이유는 최단 거리에 있는 노드를 선택하기 위함이다. 아래 예시로 설명해보면, 4로 가는 최단 거리에 있는 노드는 3이다. heapq가 없었다면, 2->4부터 계산하고 그다음에 3->4를 계산할 것이다. 그렇게 되면 4는 2번이나 이전보다 짧은 최단 거리를 만들었기 때문에, 4가 순서..
[BOJ] [Python] 14496번 : 그대, 그머가 되어
다익스트라 알고리즘을 활용하여 풀었다. 가중치 값이 1이라서 BFS로 풀어도 무방하다. # N : 문자 개수 # M : 문자쌍 # -1 : 불가능 # a : 시작 지점 # b : 찾는 지점 # 경로 : [] # 값 : [x, 0, 무한, 무한, 무한] import sys input = sys.stdin.readline start, find = map(int, input().split()) n, m = map(int, input().split()) route = [] # 경로 val = [10000000] * (n + 1) # 값 val[start] = 0 for _ in range(n + 1): route.append([]) for _ in range(m): num = list(map(int, input..
