[백준] 11725 트리의 부모 찾기

🌭 문제 설명

• 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

😎 나의 풀이

import sys
sys.setrecursionlimit(10**6) # 런타임에러 방지
N = int(sys.stdin.readline()) # 노드의 개수 N

adj = [[] for _ in range(N)] # 인접 노드 담아둘 adj

for i in range(N - 1): # N-1개의 줄에 입력을 받는다.
    a, b = map(int, sys.stdin.readline().split())
    adj[a - 1].append(b - 1) # 0부터 N-1
    adj[b - 1].append(a - 1)
    
visit = [False] * N # 방문체크 배열
parent = [0] * N # 부모노드를 담아둘 배열

# DFS
def dfs(u): 
  visit[u] = True # 방문한 노드에 True로 업데이트
  for v in adj[u]: # 인접노드 방문
    if not visit[v]: # 방문하지 않았다면
      parent[v] = u # parent배열의 해당 노드의 값을 u(부모)의 값으로 업데이트
      dfs(v) # 재귀호출 

dfs(0) # 1번 노드부터 탐색

for i in range(1, N): # 2번노드부터 출력 
  print(parent[i] + 1) # +1 을 해야 올바르게 출력됨

1. DFS 알고리즘 재귀호출을 이용한 풀이다. (주석 확인!)
   

---

🧵 다른 풀이

from collections import deque # deque(덱) 모듈을 불러와, 스택구현에 사용
import sys                                      
input = sys.stdin.readline       

N = int(input()) # 노드의 개수 N
visited = [False] * (N + 1) # 방문체크 배열, 인덱스 맞추기 위해 N+1 사용
answer = [0] * (N + 1) # 각 노드의 부모 노드를 저장할 리스트
E = [[] for _ in range(N + 1)] # 인접 리스트, 1번부터 N번까지 각 노드에 연결된 노드 저장

for i in range(N - 1): # 트리이므로 간선의 개수는 N-1개, 각 간선 정보를 입력받음
    S, D = map(int, input().split()) # S,D 입력 받음
    E[S].append(D) # S와 연결된 노드 리스트에 D 추가
    E[D].append(S) # D와 연결된 노드 리스트에 S 추가 (양방향 그래프이므로)

# DFS 스택 구현
def dfs(E, v, visited):
    visited[v] = True # 방문한 노드 True로 업데이트
    stack = deque([v]) # 스택에 시작 노드 v를 넣음

    while stack: # 스택이 빌 때까지 반복
        x = stack.pop() # 스택의 마지막 원소 x를 꺼냄 (후입선출)
        for i in E[x]: # 노드 x에 인접한 모든 노드를 순회
            if not visited[i]: # 방문하지 않았다면
                stack.append(i) # 노드 i를 스택에 추가 (나중에 방문할 예정)
                visited[i] = True # 노드 i를 방문 처리
                answer[i] = x # 노드 i의 부모 노드를 x로 기록

dfs(E, 1, visited) # 1번 노드를 시작으로 DFS 실행

for i in range(2, N + 1): # 2번 노드부터 N번 노드까지 부모 노드를 출력 (1번은 루트이므로 출력하지 않음)
    print(answer[i]) # 부모 노드 출력

1. DFS풀이 이지만, 스택으로 구현한 풀이이다. (주석 확인)

---

• 답을 제출했을 때 런타임 에러가 발생해서 보니 재귀함수의 리밋을 설정하지 않아서였다. 다른 분의 풀이를 보니 스택으로 구현하는 방법을 쓰면 런타임 에러도 안 걸리고 익숙해지면 좋은 방법인 것 같다.