시나위

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 최소 거리를 구하고 경로도 같이 구해야하는데 다익스트라 알고리즘에 경로도 같이 추가하면 쉽게 풀린다. # import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(s, e, adj_list): INF = 987654321 ret = None # dist, route ..

https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 도착지까지 최소거리를 찾아야해서 다익스트라 알고리즘을 사용해서 풀수있지만 도착지까지 갈 때 방향 전환까지 카운트해야해서 조금 까다로운 문제이다. 다익스트라 알고리즘에 진행방향과 방향을 전환한 횟수를 같이 추가해서 풀었다. import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(raser,..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 의존성을 확인하기위해 단방향 그래프를 그리고 다익스트라를 사용해서 그래프 탐색을 하면 된다. import sys; input = sys.stdin.readline from heapq import heappush, heappop def dijkstra(start, size, adj_list): ret = [0, 0] h = [(0, start)] visit = [0 for _ in range(size ..

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제를 이해하기까지 꽤 오래걸렸다. 근데 알고리즘이 어렵진 않았다. 문제를 요약하자면 각 목적지 별로 최단 경로를 찾는데 그 최단 경로 안에 g와 h 사이 도로를 포함하는 후보만 출력하는 것이다. 출발지, 교차로 g, h 에서 각 한 번 씩 최단 거리를 탐색하면 충분히 찾을수 있다. 각 지점에서 다익스트라로 최단거리를 파악하고, '출발지에서 목적지 까지'의 최단거리와 '출발지 - g - h ..

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 지난번 풀었던 문제인데 재채점된 이후에 값이 틀리게 나와서 다시 풀게되었다. import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(start, end, num_of_nodes): INF = 200_000 * 1_000 * 2 q = [] q.appen..

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 from sys import stdin;input = stdin.readline from heapq import heappop, heappush def dijkstra(start): q = [(0, start)] while q: cur_w, cur = heappop(q) if distance_matrix[i][cur] > cur_w: distance_matrix[i]..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import sys; input = sys.stdin.readline from collections import deque N, M, K, X = map(int, input().split()) linked_list = [list() for _ in range(N + 1)] for i in range(M): s, e = map..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import sys; input = sys.stdin.readline from heapq import heappop, heappush inf = 100000000 # 최대값 (max(N)-1) * max(w) N = int(input()) # 1000 M = int(input()) # 100000 link_list = [list() for _ in range(N ..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr from collections import deque def solution(N, road, K): INF = 5000000 g= [[] for _ in range(N + 1)] dist = [INF] * (N + 1) for i in range(len(road)): g[road[i][0]].append((road[i][1],road[i..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net import sys; input = sys.stdin.readline from collections import deque M, N = map(int, input().rstrip().split()) matrix = [list(map(int, list(input().rstrip()))) for _ in range(N)] visit = [[M + N] * M for _ in ra..