[백준] 3584. 가장 가까운 공통 조상 (Python)

백준 문제 풀이 - 그래프 탐색

⭐️파이썬 알고리즘 스터디 공통 문제⭐️

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

>> 4
3

💬 풀이

---

🎵 첫번째 풀이

import sys

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

def solution():

    N = int(input())        # 트리를 구성하는 노드의 수

    trees = [-1] * (N+1)        		# 각 노드의 부모
    visited = [True] + [False] * (N)   	# 노드의 방문 여부

    for _ in range(N-1):
        a, b = map(int, input().split())
        trees[b] = a

    node1, node2 = map(int, input().split())

    while not visited[node1]:
        visited[node1] = True
        if trees[node1] == -1: break
        node1 = trees[node1]
    
    while not visited[node2]:
        visited[node2] = True
        node2 = trees[node2]

    return node2

for _ in range(T):
    print(solution())

🎵 두번째 풀이

import sys

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

def solution():

    N = int(input())        # 트리를 구성하는 노드의 수

    trees = [-1] * (N+1)        # 각 노드의 부모
    visited = [True] + [False] * (N)   # 노드의 방문 여부

    for _ in range(N-1):
        a, b = map(int, input().split())
        trees[b] = a

    node1, node2 = map(int, input().split())

    visited[node1] = True
    while trees[node1] != -1:
        node1 = trees[node1]
        visited[node1] = True
    
    while not visited[node2]:
        visited[node2] = True
        node2 = trees[node2]

    return node2

for _ in range(T):
    print(solution())

✒️ 생각

---

스터디 팀원의 의견대로 수정해 본 코드 😳 더 깔끔하구만 아주좋아