본문 바로가기

전체 글27

Topology Sort from collections import dequeimport sysinput = sys.stdin.readlinev, e = map(int, input().split())indegree = [0] * (v + 1)graph = [[] for i in range(v + 1)]for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) indegree[b] += 1def topology_sort(): result = [] q = deque() for i in range(1, v + 1): if indegree[i] == 0: q.append(i) while q: .. 2024. 10. 11.
Segment Tree import sysinput = sys.stdin.readlineN, M, K = map(int, input().split())arr = []for _ in range(N): arr.append(int(input()))tree = [0] * (4 * N)minTree = [0] * (4 * N)maxTree = [0] * (4 * N)def init(node, start, end): if start == end: tree[node] = arr[start] return mid = (start + end) // 2 init(2 * node, start, mid) init(2 * node + 1, mid + 1, end) tree[node] = tree.. 2024. 10. 11.
Floyd-Warshall import sysinput = sys.stdin.readlineINF = int(1e9)n = int(input())m = int(input())graph = [[INF] * (n + 1) for _ in range(n + 1)]for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(c, graph[a][b])for k in range(1, n + 1): for a in range(1, n + 1): for b in range.. 2024. 10. 11.
Dijkstra import sysinput = sys.stdin.readlineimport heapqn = int(input())m = int(input())INF = 1e8graph = [[] for _ in range(n+1)]distance = [INF] * (n+1)for _ in range(m): u, v, w = map(int, input().split()) graph[u].append((v, w))start, end = map(int, input().split())def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop.. 2024. 10. 11.
Bellman-Ford import sysinput = sys.stdin.readlineINF = int(1e9)v, e = map(int, input().split())edges = []distance = [INF] * (v + 1)for _ in range(e): a, b, c = map(int, input().split()) edges.append((a, b, c))def bellman_ford(start): distance[start] = 0 for i in range(v): for j in range(e): cur_node = edges[j][0] next_node = edges[j][1] edge_cost = edges[j].. 2024. 10. 11.
[python] 백준 2667번 - 단지번호붙이기 0은 집이 없는 곳. 1은 집이 있는 곳. 연결된 집들끼리 이어붙인 모임을 단지라고 정의하고,그 단지의 수와 각 단지의 집 수를 오름차순으로 출력하는 문제. from collections import dequeimport sysinput = sys.stdin.readlinedef bfs(x, y): cnt = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() queue.append((x, y)) #graph[x][y] = 0 해줘야함. cnt = 1로 할 때. while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[.. 2024. 8. 15.

티스토리툴바