<최소공통조상 구하기 1>
난이도 : 골드 3
python3은 시간초과, PyPy3는 맞음. 맞았다고 하자
-
백준 문제
11437 -
코드 알고리즘
- 최소공통조상
- 11437
BFS를 실행하기 위해 인접리스트를 작성한다 (❗DFS는 런타임에러남.)
BFS 실행으로 깊이랑 각 노드의 부모노드를 찾는다
깊이를 통일 시킨 후 동시에 부모노드 올라가면서 두 노드가 일치하는 경우를 찾는다 = 최소공통조상
2-1. 슈도 코드
아래 DFS를 BFS로 바꾼후 실행
11437 슈도코드
#입력
N개 노드 입력받기
인접리스트 A 선언 #N개인 2차원 배열 리스트
for N-1줄:
a, b 입력받기
now = [a,b]로 하고 정렬하기
now[0] 부모노드에 now[1] 자식노드 삽입하기
#인접리스트 완성
#dfs 탐색하기
#tree 리스트
tree는 N+1개 리스트, 각각 2개 방을 가진 2차원 배열 #[[부모, 깊이], [부모, 깊이...]
루트노드의 부모와 깊이는 0으로 선언하기
visited 리스트 N+1개만큼 선언하기
DFS(루트노드, 깊이는 0) #루트노드로 이어진 트리이므로 한번만 시행하면 됨
#dfs to BFS
#DFS 실행하면 런타임 에러
DFS 함수(입력 노드, 깊이):
visited 체크하기
for j in 입력노드의 인접리스트:
depth = 0으로 초기화
방문 안했다면:
깊이 += 1
tree[해당노드][0] = 입력노드 #부모이므로
tree[해당노드][1] = 깊이
dfs(해당노드, 깊이)
#깊이 통일시키기
find_depth(p, q):
깊이 다를 경우: 아래 실행하기
더 깊이가 깊은 노드를 obj 로 두기
while 깊이가 같지 않을 경우:
obj의 깊이를 obj 부모노드의 깊이로 두기/ obj의 부모노드 기억하기
#이제 깊이가 같아서 빠져나온 거이므로
return 각 노드 리턴하기 #깊이가 다른 친구는 깊이가 같아진 부모노드로
깊이 같을 경우:
return 각 노드 리턴하기
for M동안:
p, q 입력받기
nodes = find_depth(p, q) #(p,q)형식으로 리턴됨
print(LCA(nodes)) 실행하기 #실행결과가 최소공통조상
#깊이 통일된 노드들끼리 LCA 실행하기
LCA(nodes):
node1 = nodes[0]
node2 = nodes[1]
while 두 노드가 일치하지 않을 경우:
node1 ] #각 노드의 부모를 자기자신으로 두기
node2
#이제 두 노드가 일치하므로
return node1 #node2 리턴해도 상관 없음- 코드
#11437
#https://www.acmicpc.net/problem/11437
import sys
sys.setrecursionlimit(5000)
input = sys.stdin.readline
from collections import deque
N = int(input()) #N개 노드
A = [[] for _ in range(N+1)] #인접리스트 선언
for i in range(N-1):
a, b = map(int, input().split())
A[a].append(b)
A[b].append(a) #BFS의 인접리스트는 양방향
#인접리스트 정렬하기
for i in range(1, N):
A[i].sort()
#BFS 탐색해서 tree 리스트 완성하기
tree = [[0, 0] for _ in range(N+1)]
#bfs 실행
visited = [False]*(N+1)
myQue = deque()
def BFS(input_node, depth):
myQue.append(input_node)
visited[input_node] = True
count = 0
now_size = 1
while myQue:
id = myQue.popleft()
for j in A[id]:
if not visited[j]:
tree[j][0] = id #부모
tree[j][1] = depth+1
#tree[j][1] = tree[id][1] + 1 #시간 초과 예상후보1
myQue.append(j)
visited[j] = True
count += 1
#큐에 들어간 원소 개수가 시행횟수랑 같을 때만 level 올려주기 (즉, level이 같은 주기때만)
if count == now_size: #현재 들어간 큐 원소 개수랑 level이 같을 경우
count = 0
now_size = len(myQue) #큐 원소 개수 업데이트
depth+=1
BFS(1,0) #루트노드는 항상 1, 루트노드의 깊이는 항상 0
#tree 완성!
#LCA 찾기
#시간초과 후보 2 복잡한 if문과 else문
def find_depth(p, q):
#항상 p를 더 깊이가 깊은 노드로 설정
if tree[p][1] < tree[q][1]: #q의 깊이가 더 깊은 경우
temp = p #잠시 p 저장
p = q #더 깊이가 깊은 q를 p로 만들기
q = temp #q 자리에 p 넣기
while tree[p][1] != tree[q][1]: #더 깊은 노드가 항상 p!
p = tree[p][0] #p를 자신의 부모노드로 바꾸기
# 이제 두 노드의 깊이가 같으므로
return (p, q)
def LCA(nodes):
node1 = nodes[0] #1번째 노드
node2 = nodes[1]
while node1 != node2:
node1 = tree[node1][0]#자기 부모
node2 = tree[node2][0]
return node1 #둘의 노드는 이제 동일하므로 node2를 리턴해도 상관 없음
M = int(input()) # 질의 개수 M개
for i in range(M):
p, q = map(int, input().split())
if tree[p][1] != tree[q][1]: #깊이가 다를 경우
nodes = find_depth(p, q) #깊이가 통일된 노드쌍
else: #깊이가 애초에 같을 경우
nodes = (p, q)
print(LCA(nodes))
- 코드 후기
- 부모노드 선택
노드 번호가 작은 노드가 부모노드가 되는 건 아니다 인접리스트를 작성시 양방향으로 작성하고 BFS 탐색시 두 노드중 누가 부모노드인지 설정되게 된다. - 런타임 에러
DFS 안된다. DFS 쓰지 말자. 런타임에러(recrusion error) 발생. 재귀 형태가 아닌 BFS를 쓰자(그냥 대부분 탐색 시 DFS보다는 BFS를 우선시 하는게 맞을듯) - 시간초과
자 BFS로 바꾸면 93%에서 시간초과라는 에러가 남아있다.
내가 수정한 것
1) BFS level을 직접 계산하기
각 노드의 부모노드를 불러와 부모노드의 깊이에 + 1을 했었는데, 이게 시간초과의 원인일까봐 고쳤다.
부모노드를 불러오지 않고 tree[j][1] = tree[id][1] + 1
BFS를 탐색하면서 level을 직접 계산했다. (*책참고)
연결방향의 수가 level과 동일하다는 것을 이용
2) if문 else문에 따라 깊이가 더 깊은 노드 찾지 말기
두 노드 중 더 깊이가 깊은 노드를 obj1으로 따로 설정해서 if문과 else문을 각각 실행했었는데
(기존 코드)
if tree[p][1] > tree[q][1]: #p의 깊이가 더 깊은 경우
obj1 = p #더 깊이가 깊은 노드를 1번째에
obj1_depth = tree[p][1]
obj2 = q
obj2_depth = tree[q][1]
else: #q의 깊이가 더 깊은 경우
obj1 = q # 더 깊이가 깊은 노드를 1번째에
obj1_depth = tree[q][1]
obj2 = p
obj2_depth = tree[p][1]temp를 사용해서 무조건 깊이가 깊은 노드를 p로 설정했다
(수정 코드)
if tree[p][1] < tree[q][1]: #q의 깊이가 더 깊은 경우
temp = p #잠시 p 저장
p = q #더 깊이가 깊은 q를 p로 만들기
q = temp #q 자리에 p 넣기하지만 아직도 왜 시간초과나는지 모르겠다(tree 리스트가 2차원 배열이라서?) 그냥 PyPy3쓰련다
for well-being we need nectar and ambrosia