[백준 11437] LCA (재풀이)

LCA 다시 풀기 (11437)

문제 출처 : https://www.acmicpc.net/problem/11437

 

사실 이 문제는 예전에 해결 했던 문제 입니다. 다만 체점이 다시 되면서 맞았던 내용이 틀렸다고 나와 다시 풀게 되었습니다. 이 전 풀이는 아래 링크를 확인 바랍니다.

https://davincicoding.tistory.com/36

[백준 11437] LCA

 

그럼 왜 틀렸는지와 그것을 해결한 방법을 알아보겠습니다.

 

일단 LCA를 더 빨리 푸는 방법은 이미 알고 있습니다. 다만 그 방법을 쓰지 않고 해결해야 하는 문제라 생각했습니다. LCA에서 부모를 이분 탐색으로 찾아 더 빨리 문제를 해결하는 방법은 아래 링크를 확인 바랍니다.

https://davincicoding.tistory.com/50

[백준 11438] LCA 2

 

이 문제에서는 위와 같이 이분 탐색을 사용하는 것이 아닌 기본적인 방법으로 문제를 해결하는 것으로 보았습니다.

문제를 보니 메모리 초과, RecursionError가 계속 나왔습니다. 어디가 맞았던 풀이인지 몰라 정확한 원인은 찾지 못했습니다.

그래서 이 상황에서 문제를 해결하는 것으로는 set_tree 부분에서 dfs가 아닌 bfs로 바꾸면 되지 않을까 생각했습니다. 아무래도 dfs보다는 bfs가 재귀를 사용하지 않기 때문에 RecursionError나 메모리 초과가 해결되지 않을까 생각했습니다. 역시나 dfs를 bfs로 변경하니 생각처럼 통과 되었습니다. 혹시라도 저처럼 LCA를 이미 해결하였는데 다시 실패가 떴다면 set_tree 부분을 수정해 보시기 바랍니다.

코드 작성

그럼 오랜만에 LCA 문제를 다시 한번 해결해 보겠습니다.

입력 받기

mii = lambda : map(int, input().split())
N = int(input())

tree = [[] for _ in range(N+1)]

for _ in range(N-1):
    u, v = mii()
    tree[u].append(v)
    tree[v].append(u)

노드의 개수 N을 입력 받은 후 N - 1개 줄의 두 정점 정보를 입력 받습니다. 입력 받은 u, v 정보로 tree를 구성합니다.

트리 만들기

다음으로 dfs 부분을 bfs로 바꿔준 부분 입니다. 입력 받은 그래프 정보를 가지고 트리를 만들어 주었습니다.

from collections import deque

parent = [0] * (N+1)
level = [0] * (N+1)

def set_tree(s):
    que = deque([s])
    level[s] = 1
    while que:
        node = que.popleft()
        
        for child in tree[node]:
            if level[child]:
                continue
        
            level[child] = level[node] + 1
            parent[child] = node 
            que.append(child)

set_tree(1)

parent에는 각 정점의 부모 정보가 들어있고, level에는 현재 노드의 깊이가 들어 있습니다.

최소 공통 조상 찾기

def lca(a, b):
    while level[a] != level[b]:
        if level[a] < level[b]:
            b = parent[b]
        else:    
            a = parent[a]
    
    while a != b:
        a = parent[a]
        b = parent[b]
    
    return a

두 노드의 깊이를 맞춰 최소 공통 조상을 찾는 로직 입니다. 먼저 두 노드의 깊이를 맞춰 주어야 합니다. level[a]와 level[b]의 깊이 중 더 아래에 있는 것을 다른 노드의 깊이와 똑같이 맞춰주는 역할을 합니다.

두 노드의 깊이가 같게 된다면 다음으로 최소 공통 조상을 찾습니다. 부모 노드를 따라 올라가 a와 b 값이 같아진다면 그 값이 바로 최소 공통 조상이 됩니다.

출력하기

M = int(input())
for _ in range(M):
    u, v = mii()
    print(lca(u, v))

마지막으로 출력하는 부분 입니다. 먼저 두 노드의 쌍의 개수 M을 입력 받습니다. M번 반복을 통해 두 노드 u, v 값의 최소 공통 조상을 찾아 출력해 주면 됩니다.

전체 코드

전체 코드 입니다.

from collections import deque

mii = lambda : map(int, input().split())
N = int(input())

tree = [[] for _ in range(N+1)]
parent = [0] * (N+1)
level = [0] * (N+1)

for _ in range(N-1):
    u, v = mii()
    tree[u].append(v)
    tree[v].append(u)

def set_tree(s):
    que = deque([s])
    level[s] = 1
    while que:
        node = que.popleft()
        
        for child in tree[node]:
            if level[child]:
                continue
        
            level[child] = level[node] + 1
            parent[child] = node 
            que.append(child)

def lca(a, b):
    while level[a] != level[b]:
        if level[a] < level[b]:
            b = parent[b]
        else:    
            a = parent[a]
    
    while a != b:
        a = parent[a]
        b = parent[b]
    
    return a

set_tree(1)

M = int(input())
for _ in range(M):
    u, v = mii()
    print(lca(u, v)) 

이미 예전에 풀었던 문제라 자세한 설명은 하지 않았습니다. 이렇게 오래 전에 풀었던 문제를 다시 풀어보는 것도 도움이 많이 됩니다. 풀어본지 한 달 이상 지났다면 다시 한 번 문제를 풀어보시기 바랍니다.