[문제풀이]백준_11725_트리 부모 찾기(DFS)

• 알고리즘 유형 : 그래프, 탐색, DFS
• 풀이 참고 : 스스로
• 문제 링크 : https://www.acmicpc.net/problem/11725

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

풀이 요약

1. DFS 와 BFS의 개념만 정확히 이해 필요

  - 내가 정리한 링크 : https://kyyu.tistory.com/26

2. 내가 풀었기에 이부분만 이해 하면 누구나 풀수있다.

[DFS/BFS]백준_1260_DFS와 BFS(이론 정리)

3. 키포인트

  - 위 1260번 문제에서 추가된 개념은 다음과 같다.

  1) 엣지의 개수가 주어지지 않아 while문으로 input을 받은 부분

  2) 부모 노드를 찾아야 하기에 추가적인 체크 리스트를 만든 것

---

코드(python)

import sys
sys.setrecursionlimit(10**7)

# 노드의 개수 n
n = int(input())
# 주어진 노드의 연결 정보를 담기 위한 2중 리스트
arr = [[] for _ in range(n+1)]

# 엣지의 개수가 주어 지지 않아서 while문으로 엣지정보를 받음 
count1 = 0
while count1 <= 100000:
    try:
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)
        count1 += 1
    except:
        break

# 노드 기준으로 정렬
for i in range(len(arr)):
    arr[i].sort()
tree = arr
# tree = [[], [4, 6], [4], [5, 6], [1, 2, 7], [3], [1, 3], [4]]

# 방문 노드를 체크 하기위한 visited
visited = [0] * (n+1)
# visited = [0,1,0,0,0,0,0]

# 부모 노드를 체크 하기 위해
parents = [0] * (n+1)

# dfs 재귀
def dfs(start_node):
    visited[start_node] = start_node
    for i in tree[start_node]:
        if i != visited[i]:
            visited[i] = i
            dfs(i) 
        else:  
            # 방문 했던 노드이면 parents에 노드 추가
            parents[start_node] = i 
            continue
dfs(1)

for i in range(2, len(parents)):
    print(parents[i])

---

배운 점, 배울 점

1. 역시 관련 문제를 많이 풀어 보는 것이 개념이해에 도움이 된다. 문제 푸는 개수를 늘리자.

2. 재귀 문제 하나 풀고 자기