본문 바로가기

알고리즘22

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.
[python] 백준 2630번 - 색종이 만들기 모두 같은 색이 나올 때 까지 색종이를 잘라서 각각의 종이의 개수를 구하는 분할정복 문제이다. import sysinput = sys.stdin.readlinedef f(x, y, N): global white, blue c = paper[x][y] same_color = True for i in range(x, x + N): for j in range(y, y + N): if c != paper[i][j]: same_color = False break if not same_color: break if same_color: if c =.. 2024. 8. 11.
[python] 백준 11279번 - 최대 힙 최대 힙을 구현하는 문제. import sysimport heapqinput = sys.stdin.readlineN = int(input())heap = []for _ in range(N): x = int(input()) if x == 0: if len(heap) > 0: print(-heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap, -x)heapq 모듈을 사용하면 힙 자료구조를 간편하게 사용할 수 있지만,최소 힙밖에 제공되지 않는다. 따라서 최대 힙을 구현하기 위해서는 원소를 저장할 때 마이너스 부호를 붙여간단하게 최대 힙을 구현할 수 있다. 2024. 8. 11.

티스토리툴바