정화 코딩

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..

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..

A. 여러분의 다리가 되어 드리겠습니다! (백준 17352번) https://www.acmicpc.net/problem/17352 #python from sys import stdin import sys sys.setrecursionlimit(100000) def find(a): if parent[a] == a: return a else: parent[a] = find(parent[a]) return parent[a] def union(a, b): a = find(a) b = find(b) if a != b: parent[b] = a n = int(stdin.readline()) parent = [i for i in range(n+1)] for _ in range(n-2): a, b = map(int, ..