본문 바로가기
반응형

{ Problem Solving }/Dijkstra & Floyd-Warshall14

[다익스트라/파이썬] 백준 9370번 : 미확인 도착지 / 골드 2 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import sys import collections import heapq input = sys.stdin.readline t = int(input()) for _ in range(t): n, m, t = map(int, input().split()) # 교차로, 도로, 목적지 후보 개수 s, g, h = map(int, input().split()) # s 출발지, g -> h graph.. 2022. 3. 6.
[다익스트라] 백준 266번: 미로만들기 / 골드 4 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net import heapq n = int(input()) table = [] for _ in range(n): table.append([int(x) for x in input()]) visited = [] for _ in range(n): visited.append([False for _ in range(n)]) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] q = [] star.. 2022. 3. 5.
[최단 경로] 백준 2206번 : 벽 부수고 이동하기 / 골드 4 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net import heapq x_lim, y_lim = map(int, input().split()) # edge case if x_lim == 1 and y_lim == 1: print(1) quit() table = [] for _ in range(x_lim): table.append([int(x) for x in input()]) dx = [-1, 1, 0, 0] dy =.. 2022. 2. 19.
[최단 경로] 백준 11779번 : 최소비용 구하기 2 / 골드 3 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 + 경로 직접 구하기 문제이다. 힙에 cost + w, next 뿐만 아니라 cur 노드도 넣어준다. 그리고 힙에서 하나씩 꺼내면서 처음 방문한 노드에 도착하면 딕셔너리 구조에 이전 노드, 현재 노드를 저장해준다. 다익스트라가 끝난 후 딕셔너리를 이용해 목적지부터 역순으로 경로를 추적하면 된다. 웰노운 문젠데 좀 오래 걸렸다.. 정신차리자. import .. 2021. 12. 3.
[ 최단 경로 ] 백준 14938번: 서강그라운드 / 골드 4 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net sol 1) 다익스트라 import heapq import collections n, m, r = map(int, input().split()) items = list(map(int, input().split())) graph = collections.defaultdict(list) for _ in range(r): u, v, w = map(int, input().split()) # start, end.. 2021. 7. 21.
[최단 경로] 백준 4485번: 녹색 옷 입은 애가 젤다지? / 골드 4 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net import sys import heapq def dijkstra(): global answer q = [] heapq.heappush(q, [graph[0][0], 0, 0]) # cost, x, y while q: cost, x, y = heapq.heappop(q) if n*x+y not in visited: visited[n*x+y] = cost if x == n-1 an.. 2021. 6. 8.
반응형

티스토리툴바