[백준] 3584 가장 가까운 공통 조상

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

노드들의 연결 관계를 먼저 정리한 이후, 두 노드를 큐에 담았습니다.

두 노드를 번갈아가며 부모 노드들을 모두 탐색하였습니다.

탐색 중 이미 방문한 노드인 경우가 공통 조상 노드이기 때문에 해당 노드를 반환하였습니다.

2) 알고리즘

• DFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

def solution(a, b):
    visited = [False] * N                   # 노드 방문 여부
    q = deque([a, b])                       # 큐, 초기에 시작할 두개의 노드

    while q:        
        node = q.popleft()
        if not visited[node]:               # 아직 탐색하지 않은 노드라면
            visited[node] = True            # 해당 노드 탐색 완료
            for next in linked[node]:       # 부모 노드 탐색
                q.append(next)
        else:                               # 이미 탐색한 노드라면, 공통 조상
            return node

T = int(sys.stdin.readline())               # 테스트 케이스 수

for _ in range(T):
    N = int(sys.stdin.readline())           # 노드의 개수
    linked = [[] for _ in range(N)]         # 연결 관계

    for _ in range(N-1):
        a, b = map(int, sys.stdin.readline().split())
        linked[b-1].append(a-1)                         # B 노드의 부모는 A 노드

    A, B = map(int, sys.stdin.readline().split())       # 탐색할 두개의 노드

    print(solution(A-1, B-1) + 1)           # 탐색 및 반환값 출력

---

🔗 문제 링크

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

3584번: 가장 가까운 공통 조상

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다