정화 코딩

09-5. 최소 공통 조상 074. LCA (백준 11437번) https://www.acmicpc.net/problem/11437 import sys from collections import deque input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] depth = [0] * (n+1) parent = [0] * (n+1) visited = [False] * (n+1) def bfs(node): que = deque() que.append(node) visited[node] = True level = 1 size = 1 cnt = 0 while que: now = que.popleft() for nxt in tree..

A. 완전 이진 트리 (백준 9934번) https://www.acmicpc.net/problem/9934 #python import sys input = sys.stdin.readline k = int(input()) visit = list(map(int, input().split())) tree = {} for i in range(1, pow(2, k-1)): tree[i] = [i*2, i*2 + 1, 0] for i in range(pow(2, k-1), pow(2, k)): tree[i] = ['.', '.', 0] def inOrder(now): global i if now != '.': inOrder(tree[now][0]) tree[now][2] = visit[i] i += 1 inOrde..

09-3. 이진 트리 070. 트리 순회 (백준 1991번) https://www.acmicpc.net/problem/1991 from sys import stdin n = int(stdin.readline()) tree = {} for _ in range(n): self, left, right = stdin.readline().split() tree[self] = [left, right] def preOrder(now): if now != '.': print(now, end='') preOrder(tree[now][0]) preOrder(tree[now][1]) def inOrder(now): if now != '.': inOrder(tree[now][0]) print(now, end='') inOrd..

09-1. 트리 알아보기 067. 트리의 부모 찾기 (백준 11725번) https://www.acmicpc.net/problem/11725 from sys import stdin import sys sys.setrecursionlimit(10 ** 6) n = int(stdin.readline()) g = [[] for _ in range(n+1)] parent = [0] * (n+1) def dfs(pre, cur): for nxt in g[cur]: if nxt != pre: parent[nxt] = cur dfs(cur, nxt) for _ in range(n-1): a, b = map(int, stdin.readline().split()) g[a].append(b) g[b].append(a) d..

A. 호석이 두 마리 치킨 (백준 21278번) https://www.acmicpc.net/problem/21278 #python from sys import stdin import sys n, m = map(int, stdin.readline().split()) g = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)] for i in range(1, n+1): g[i][i] = 0 for _ in range(m): a, b = map(int, stdin.readline().split()) g[a][b] = 1 g[b][a] = 1 for i in range(1, n+1): # 경유지 i에 대해 for j in range(1, n+1): # 출발 노드 j..

08-6. 플로이드-워셜 061. 플로이드 (백준 11404번) https://www.acmicpc.net/problem/11404 from sys import stdin import sys n = int(stdin.readline()) m = int(stdin.readline()) g = [[sys.maxsize for _ in range(n+1)] for _ in range(n+1)] for i in range(n+1): g[i][i] = 0 for _ in range(m): a, b, c = map(int, stdin.readline().split()) if c < g[a][b]: g[a][b] = c for i in range(1, n+1): # 경유지 i에 관해 for j in range(1, ..

A. 지름길 (백준 1446번) https://www.acmicpc.net/problem/1446 #python from sys import stdin import sys from queue import PriorityQueue n, d = map(int, stdin.readline().split()) g = [[] for _ in range(10001)] visited = [False] * (10001) dst = [sys.maxsize] * (10001) que = PriorityQueue() for i in range(d): g[i].append((i+1, 1)) for _ in range(n): a, b, c = map(int, stdin.readline().split()) g[a].append(..

08-4. 다익스트라 056. 최단경로 (백준 1753번) https://www.acmicpc.net/problem/1753 from sys import stdin from queue import PriorityQueue import sys v, e = map(int, stdin.readline().split()) g = [[] for _ in range(v+1)] dst = [sys.maxsize] * (v+1) visited = [False] * (v+1) que = PriorityQueue() start = int(stdin.readline()) dst[start] = 0 que.put((0, start)) for _ in range(e): a, b, c = map(int, stdin.readlin..