[BOJ / 백준] 3584 가장 가까운 공통 조상 (G4 / 트리) - Python

링크

https://www.acmicpc.net/problem/3584

 

 

 

 

문제 해석

테스트 케이스 별로 공통 조상 노드를 구하라

 

공통 조상 노드란 a, b가 서로 만나는 조상이면서 가장 가까운 조상을 의미한다. 

 

 

입력

첫 번째 줄 : t
  t : 테스트 케이스 개수


<테스트 케이스별>
첫 번째 줄 : n
  n : 트리의 노드 수

n - 1개의 줄 : a, b
  a : 부모
  b : 자식

마지막 줄 : n1, n2
  n1, n2 : 공통 조상을 찾을 두 노드

 

출력

각 테스트 케이스의 공통 조상 노드 출력 

 

 

 

풀이 & 코드 해석

그래프 문제는 누가 누구의 부모이고 자식인지 등 그래프의 형태를 파악하기 위해 연결을 할 필요가 있습니다.

 

다만 해당 문제는 입력 시 a 노드가 b 노드의 부모이다 라는 조건을 제시해주고 있으므로, 그래프의 형태가 이미 완성되어 있다고 판단하였습니다.

 

 

따라서 저는 그래프 배열에 내 부모 정보를 저장하도록 만들었습니다. 

 

만약 3 5 와 같은 정보가 들어오면 graph[5] 에는 3이 저장되어 있을 것입니다.

 

 

우리는 두 노드 n1, n2의 공통 조상 노드를 찾아야 합니다.

 

그래서 n1의 조상은 누가 있는지를 루트 노드까지 쫒아 올라가면서 리스트에 저장합니다.

 

다음 n2를 마찬가지로 루트 노드까지 쫒아가는데, n1의 리스트에 탐색하는 노드의 번호가 있다면 가장 먼저 공통 노드를 만나는 것이므로 정답으로 출력하고 종료하였습니다.

 

 

 

 

코드

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())

    graph = [[] for _ in range(n + 1)]

    for _ in range(n - 1):
        a, b = list(map(int, input().split()))
        graph[b].append(a)

    n1, n2 = list(map(int, input().split()))

    ans_list = [] # n1이 부모로 가질 수 있는 리스트

    nxt = n1
    while nxt != 0:
        ans_list.append(nxt)

        if len(graph[nxt]) == 0:
            nxt = 0
        else:
            nxt = graph[nxt][0]

    nxt = n2
    while nxt != 0:
        if nxt in ans_list:
            print(nxt)
            break

        if len(graph[nxt]) == 0:
            nxt = 0
        else:
            nxt = graph[nxt][0]

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java