1. 문제 출처 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이 기본적인 데이크스트라 알고리즘을 사용하는 문제이다. 변형된 점은 인접한 노드를 구할 때 리스트나 메트릭스를 이용하는 것이 아닌 , 해당 좌표의 상하 좌우를 가지고 온다는 것이다. # 데이크스트라 알고리즘을 위한 힙 모듈 불러오기 import heapq # 입력 result = [] n = int(input()) while n!=0: #입력 graph =..
1. 문제 출처 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 2. 풀이 데이크스트라를 1->v1->v2->n or 1->v2->v1->n 순으로 3번 사용해야 한다. 해당 해답은 pypy3 로 실행 하였다. import heapq #입력 n,e = map(int,input().split()) graph = [[] for _ in range(n+1)] # 입력 for _ in range(e): a,..
1. 문제 출처 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 풀이 각 노드를 시작점으로 경로를 구해줘야 한다. import heapq # 입력 n,m,x = map(int, input().split()) graph = [[] for _ in range(n+1)] distance = [[float('inf')] * (n+1) for _ in range(n+1)] # 입력 for _ in range(m): s..
1. 문제 출처 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 데이크스트라 알고리즘을 이용한 문제이다... 여기서 주의 할점은 그래프 배열의 사이즈를 max(n,k)로 하는 것이아니라 100000로 해야한다. 왜냐하면 max 를 사용해서 지정 할경우 해당 범위를 지나서 도착하는 것이 더빠를 수 있는데 그것을 계산하지 못하기 때문이다. import heapq #입력 n,k = map(int, inpu..
1. 문제 출처 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 풀이 단순 데이크스트라 알고리즘을 이용하는 문제이다. import sys input = sys.stdin.readline import heapq # 최대값 정의 INF = float('inf') # 입력 n = int(input()) m = int(input()) # 그래프와 거리 초기화 graph = [[] for _ in range(n+1..
1. 문제 출처 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 풀이 데이크스트라를 사용하는 문제이다. 데이크스트라 알고리즘은 별로 사용한 적이 없어서 많이 해멘던 것 같다. 그래프 자료 구조를 사용하여 weights ,node, edge 를 구현 하였고 해당 구조를 사용하여 데이크스트라 알고리즘 을 사용하기 위해 우선순위큐를 구현해야 했다. 이 우선순위 큐를 구현하기 위해 heap 구조를 사용하였다...
