목록전체 글 (271)

흙금이네 블로그

[BOJ] 1368 - 물대기 (Python)

아이디어 크루스칼 알고리즘으로 최소 스패닝 트리를 구현하여 최소 비용을 구한다. 풀이 가상의 0번째 논을 설정해 우물을 팔 때 드는 비용을 0번 논과 연결하는 데 드는 비용으로 저장하여 푼다. import sys input = sys.stdin.readline INF = int(1e8) def solution(): def find(n): temp = n while n != group[n]: n = group[n] group[temp] = n return n def union(n1, n2): n1 = find(n1) n2 = find(n2) if n1 > n2: n1, n2 = n2, n1 group[n2] = n1 N = int(input()) group = [i for i in range(N+1)] e..
알고리즘 2023. 4. 15. 00:10
[BOJ] 10423 - 전기가 부족해 (Python)

아이디어 최소 스패닝 트리로 모든 도시에 전기를 공급할 수 있는 최소 비용을 구한다. 풀이 #1 프림 알고리즘으로 최소 스패닝 트리를 구현한다. import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e7) def solution(): N, M, K = map(int, input().split()) plant = tuple(map(int, input().split())) graph = [dict() for _ in range(N+1)] for _ in range(M): u, v, w = map(int, input().split()) graph[u][v] = graph[v][u] = min(graph[u].ge..
알고리즘 2023. 4. 15. 00:03
[BOJ] 1865 - 웜홀 (Python)

아이디어 벨만-포드로 음의 사이클이 존재하는지 확인한다. 풀이 도로는 방향이 없고 웜홀은 방향이 있음에 주의해야 한다. import sys input = sys.stdin.readline INF = int(1e11) def solution(): TC = int(input()) for _ in range(TC): N, M, W = map(int, input().split()) graph = [dict() for _ in range(N+1)] for _ in range(M): S, E, T = map(int, input().split()) graph[S][E] = min(graph[S].get(E, INF), T) graph[E][S] = min(graph[E].get(S, INF), T) for _ in ..
알고리즘 2023. 4. 14. 23:57
이전 Prev 1 ··· 24 25 26 27 28 29 30 ··· 91 Next 다음