느낌표 공장

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 과정 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 하므로, 공장 두 곳을 이은 다리들 중 중량 제한이 더 큰 다리를 건너는 것이 좋다. 따라서 입력받은 다리 정보들을 다리의 중량 제한을 기준으로 하여 내림차순으로 정렬하고, 다익스트라를 사용하되 힙에 push 할 때, 중량을 마이너스를 붙여 push 하여 최대..

문제 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 풀이과정 컴퓨터와 시간을 주고 최소 시간으로 모든 컴퓨터를 연결해야 한다. 그리고 연결하는 횟수와 연결할 컴퓨터의 번호를 출력하는 문제이다. 따라서 노드와 거리(시간)이 있고 최단 거리 찾기라고 생각하여 다익스트라 알고리즘을 활용하여 풀었다. 처음에는 for문으로 dijkstra 함수를 모든 컴퓨터에서 시작시켜서 거기서 가장 시간이 적게 드는 곳을 연결해야지 라고 ..

import heapq def dijkstra(): dist = [float('inf') for _ in range(n+1)] # 가중치 초기화 queue = [[0, a]] # 횟수, 시작 문자 넣기 dist[a] = 0 # 시작지점 가중치 0 while queue: d, now = heapq.heappop(queue) # 현재까지 치환 횟수, 현재 문자 뽑기 if now == b: # 바꾸려고 하는 문자 b라면 print(d) # 현재까지 치환 횟수 출력 return if dist[now] < d: # 저장한 치환횟수보다 꺼낸게 더 크다면 패스 continue for next in visited[now]: # 현재 문자에서 바꿀 수 있는 문자로 가보기 nd = d + 1 # 치환 횟수 + 1 if n..

import heapq # 방향 벡터 dy = [1, -1, 0, 0] dx = [0, 0, 1, -1] def dijkstra(): queue = [[rupee[0][0], 0, 0]] # 탐험 할 곳 담아둘 리스트 # 시작지점 루피, y좌표, x좌표 넣기 visited[0][0] = rupee[0][0] # 시작지점 루피 while queue: d, y, x = heapq.heappop(queue) # 현재까지 잃은 루피, 현재 좌표 꺼내기 if y == n-1 and x == n-1: # 동굴 출구까지 왔다면 현재까지 잃은 루피 출력 print(f'Problem {tc}: {d}') return if visited[y][x] < d: # 현재까지 잃은 루피가 저장되어 있는 루피보다 크다면 패스 co..

import heapq def dijkstra(s, e): dist = [float('inf') for _ in range(n+1)] # 경로 시간 초기화 queue = [] heapq.heappush(queue, [0, s]) # 시작 지점 넣어주기 dist[s] = 0 # 시작지점의 길이 0으로 설정 (시작 -> 시작 의 시간은 0) while queue: d, now = heapq.heappop(queue) # 현재까지의 시간과 현재 마을 꺼내기 if now == e: # 도착지점이면 시작 -> 현재 마을까지 최단 거리 return return d # 학생 마을 -> x 로 갈때만 해당 if dist[now] < d: # 현재 마을까지 걸리는 저장된 시간보다 꺼낸 시간이 더 크다면 pass cont..

import heapq def dijkstra(s, e): dist = [float('inf') for _ in range(n + 1)] # 초기화 queue = [] heapq.heappush(queue, [0, s]) # 시작 지점 넣기 dist[s] = 0 while queue: d, now = heapq.heappop(queue) # 거리, 현재 정점 if now == e: # 도착 정점이면 중단 break if dist[now] < d: # 가지치기 continue for next in visited[now]: # 현재 정점에서 갈 수 있는 정점 탐방 nd = next[1] + d # 거리 더해주기 if nd < dist[next[0]]: # 출발 정점 ~ 다음 정점까지의 거리보다 작다면 dis..

Dijkstra 알고리즘이란 ? 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 음의 간선이 존재하지 않는, 간선의 값이 0 이상의 양수일 때 정상적으로 동작한다. 우선 순위 큐(heapq)를 사용한다. 동작 원리 단계 인접 리스트를 만든다. 최단 거리 테이블을 무한대의 값으로 초기화한다. 현재 노드에서 갈 수 있는 노드 다 가져온다. 현재 노드에서 다음 노드로 가는 간선 비용을 계산하여 가중치 테이블을 업데이트 한다. 3번과 4번을 반복한다. 문제 SWEA - 5251. 최소이동거리

import heapq tc = int(input()) for idx in range(1, tc+1): n, e = map(int, input().split())# 노드의 개수 n, 간선의 개수 e temp = [list(map(int, input().split())) for i in range(e)]# 출발노드, 도착노드, 가중치 받아오기 dist = [999999999 for i in range(n+1)]# 모든 노드 가중치 무한대로 초기화 visited = [[] for i in range(n+1)]# 인접 리스트 만들기 for i in temp: visited[i[0]].append([i[1], i[2]])# 단방향, 가중치와 함께 저장한다. que = [] heapq.heappush(que, [..