Algorithm/Graph188 [파이썬] 백준 1956 : 운동 (골드4) [파이썬] 백준 1956 : 운동 (골드4)https://www.acmicpc.net/problem/1956풀이방향성 생각사이클이 a -> b -> a로도 생긴다는 것을 알려줌.N = 400이라 N^3으로도 가능한 플로이드워셜 사용다익같은 경우, 간선이 N^^2까지 주어져서 시간/메모리 관리를 빡빡하게 해야할듯..전체코드import sysinput = lambda : sys.stdin.readline().rstrip()INF = sys.maxsizeN,M = map(int,input().split())G = [[INF]*(N+1) for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a][b] = cost# 초.. 2025. 1. 5. [파이썬] 백준 1238 : 파티 (골드3) [파이썬] 백준 1238 : 파티 (골드3)https://www.acmicpc.net/problem/1238풀이방향성 생각모든 노드에 대해서 다익스트라 돌려서 걸리는 시간 얻기. 전체코드import heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = float('inf')N,M,X = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost))def di(x): V = [INF]*(N+1) V[x] = 0 heap = [(0,x)] .. 2025. 1. 4. [파이썬] 백준 13911 : 집 구하기 (골드2) [파이썬] 백준 13911 : 집 구하기 (골드2)https://www.acmicpc.net/problem/13911 풀이방향성 생각다익스트라맥도날드 따로, 스타벅스 따로 다익스트라를 돌린다.전체코드from collections import defaultdict as ddimport heapq as hqimport sysinput = lambda : sys.stdin.readline().rstrip()INF = float('inf')N,M = map(int,input().split())G = [[] for _ in range(N+1)]for _ in range(M): a,b,cost = map(int,input().split()) G[a].append((b,cost)) G[b].appen.. 2025. 1. 3. [파이썬] 백준 16398 : 행성 연결 (골드4) [파이썬] 백준 16398 : 행성 연결 (골드4)https://www.acmicpc.net/problem/16398풀이방향성 생각최소 비용으로 모든 노드 연결 -> MST 기본.입력이 인접행렬식으로 주어진다.대칭이라서 순회만 상삼각으로 훑어준다.전체코드N = int(input())# 상삼각 읽기matrix = [tuple(map(int,input().split())) for _ in range(N)]G = []for i in range(N): for j in range(i+1,N): G.append((i,j,matrix[i][j]))G.sort(key=lambda x:-x[2])P = [i for i in range(N+1)]def find(x): if P[x] != x: .. 2025. 1. 2. 이전 1 ··· 13 14 15 16 17 18 19 ··· 47 다음
