Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 문자열
- 정수론
- DFS
- 싸피
- DP
- 애드 혹
- 정렬
- 모던 JavaScript 튜토리얼
- 이분 탐색
- boj
- 수학
- 구현
- 그래프
- Python
- BFS
- 세그먼트 트리
- 해시 테이블
- 맵
- 누적 합
- JavaScript
- 13164
- 플로이드-워셜
- 에라토스테네스의 체
- 슬라이딩 윈도우
- 그리디
- 브루트포스
- 투 포인터
- SSAFY
- 2357
- 트리
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 11437 - LCA (Python) 본문
아이디어
최소 공통 조상 알고리즘을 이용해 가장 가까운 공통 조상을 알아낸다.
풀이
너비 우선 탐색 함수 bfs에서는 트리를 탐색하며 현재 노드의 깊이, 부모 노드를 저장하도록 한다.
최소 공통 조상을 찾는 함수 find는 두 노드의 깊이를 일정하게 맞춘 뒤, 공통 조상을 찾아 반환한다.
딕셔너리 memo에는 이미 조상을 찾았던 두 노드의 최소 공통 조상을 저장해두어 find 함수를 재호출하지 않도록 한다.
입력 받은 간선들을 2차원 리스트 graph에 추가한 후, 함수 bfs를 호출하여 노드 깊이와 부모 노드 정보를 저장한다.
M개의 두 노드에 대한 최소 공통 조상을 찾아 출력하고, 메모이제이션을 통해 실행 시간을 단축한다.
import sys
input = sys.stdin.readline
def bfs():
queue = [1]
visited[1] = 1
while queue:
idx = queue.pop(0)
for i in graph[idx]:
if not visited[i]:
depth[i] = depth[idx] + 1
parent[i] = idx
queue.append(i)
visited[i] = 1
def find(a, b):
if depth[a] > depth[b]:
a, b = b, a
while depth[b] > depth[a]:
b = parent[b]
while a != b:
a = parent[a]
b = parent[b]
return a
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
parent = [0]*(N+1)
depth = [0]*(N+1)
visited = [0]*(N+1)
bfs()
M = int(input())
memo = dict()
for _ in range(M):
a, b = map(int, input().split())
if not memo.get((a, b), 0):
memo[(a, b)] = memo[(b, a)] = find(a, b)
print(memo.get((a, b)))
메모이제이션을 적용하지 않으면 Python 3로는 시간 초과가 나고, PyPy3로 겨우 통과할 수 있었다.
# 더 느린 코드
M = int(input())
for _ in range(M):
a, b = map(int, input().split())
print(find(a, b))
'알고리즘' 카테고리의 다른 글
[BOJ] 11812 - K진 트리 (Python) (0) | 2023.01.10 |
---|---|
[BOJ] 17435 - 합성함수와 쿼리 (Python) (0) | 2023.01.09 |
[BOJ] 1253 - 좋다 (Python) (0) | 2023.01.07 |
[BOJ] 6497 - 전력난 (Python) (1) | 2023.01.07 |
[BOJ] 2696 - 중앙값 구하기 (Python) (0) | 2023.01.06 |
Comments