흙금이네 블로그

아이디어 전화를 넘겨 받을 수 있는 부원을 선행으로 위상 정렬하여 진입 차수가 0이 되는 부원의 수를 구한다. 풀이 진입 차수가 0이 되지 않는 부원들은 사이클이 발생하는 구간에 존재한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) graph = [dict() for _ in range(N+1)] D = [0]*(N+1) for _ in range(M): U, V = map(int, input().split()) if graph[V].get(U, 0) == 0: graph[V][U] = 1 D[U] += 1 stack = [] for i in range(1, N+1): if D[i] == 0:..

아이디어 다익스트라로 2번 정점까지의 최단 거리를 구한 후, 트리에서의 동적 계획법으로 경로의 수를 구한다. 풀이 import sys from heapq import heappush, heappop sys.setrecursionlimit(int(1e5)) input = sys.stdin.readline INF = int(1e7) def solution(): def dfs(u): if dp[u]: return dp[u] if u == 2: return 1 for v, c in graph[u]: if D[v] < D[u]: dp[u] += dfs(v) return dp[u] N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] for _ in ..

아이디어 크루스칼 알고리즘으로 최소 스패닝 트리를 구현하되, 고려하지 않아도 될 터널들은 제외하여 시간을 단축한다. 풀이 좌표 x, y, z 각각을 기준으로 행성들을 정렬하여 인접한 두 행성과 두 행성을 연결하는 데 필요한 비용만을 고려한다. import sys input = sys.stdin.readline 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()) planets = [] for i i..