[Python][백준] 11725. 트리의 부모 찾기 / 트리,재귀,DFS,BFS (S2)

🔗링크 :  

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

---

해당 문제는 BFS, DFS 방식 모두 다 풀 수 있다 .

🗒️BFS 풀이

import sys
from collections import deque

N = int(sys.stdin.readline())
node = [[] for _ in range(N + 1)]
parents = [0] * (N + 1)
parents[1] = 1

for i in range(1, N + 1):
    node[i] = []

for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    node[a].append(b)
    node[b].append(a)

q = deque([1])

while q:
    v = q.popleft()
    for i in node[v]:
        if parents[i] == 0:
            parents[i] = v
            q.append(i)

for i in range(2, N + 1):
    print(parents[i])

 

1. 먼저 입력을 받고, node 연결 리스트 생성하고, parents를 각 노드 별 만들어준다.

(parents[1] = 1 인 이유는 트리의 루트를 1로 설정해서) 

 

2. 그리고  연결된 각 노드를 입력받아 연결 리스트에 넣어준다. 

 

3. q를 루트 노드인 1 부터 시작한다. 

 

4. 루트 노드인 1부터 시작해서, 1의 자식들을 구해준다. 

1의 자식들은 다른 노드의 부모가 되기 때문에 q에 넣어서 자식을 찾아준다. 

 

5. 이제 완성된 parents를 출력해주면 된다.

 

 

🗒️DFS 풀이

import sys
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
node = [[] for _ in range(N + 1)]
parents = [0] * (N + 1)
parents[1] = 1

for i in range(1, N + 1):
    node[i] = []

for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    node[a].append(b)
    node[b].append(a)

def dfs(n):
    for i in node[n]:
        if parents[i] == 0:
            parents[i] = n
            dfs(i)
dfs(1)

for i in range(2, N + 1):
    print(parents[i])

 

BFS에서 2번까지 똑같은 내용이다. 

 

1. dfs 같은 경우 1의 자식을 먼저 찾고, 

한 자식의 자식을 재귀돌려서 부모들을 각각 찾아준다. 

 

(그야말로 BFS와 DFS 차이 ... )

 

 

🔧 내가 작성한 코드 1

N = int(input())

class Node():
    def __init__(self,item,parent):
        self.item = item
        self.parent = parent

tree = {}

for i in range(1,N+1):
    tree[i] = Node(i,None)

tree[1].parent = 1 

for _ in range(N-1):
    x,y = map(int,input().split())
    if tree[x].parent : 
        tree[y].parent = x
    else : 
        tree[x].parent = y

for i in range(2,N+1):
    print(tree[i].parent)

내가 작성한 코드에서는 먼저 class를 만들어준다. 그리고 node 값에 맞는 객체를 만들어주어 item을 정의한다.

 

반복문을 통해 각 노드의 x의 부모가 있는지 확인해준다.

만일 부모가 있는 경우, y의부모는 x가 되는 것이다.반대의 경우는 x가 y의 부모가 된다.  

 

→  이렇게 했을 때 예제 입력은 다 맞게 출력이 된다.

하지만 무조건 연결 노드 입력의 시작이 무조건 1 이 포함되어야 한다... 

 만일 처음 시작이 "6 3"  이런 경우는 올바르지 않은 값들이 나오게 된다. 

 

🔧 내가 작성한 코드 2

import sys
sys.setrecursionlimit(10**6)
N = int(sys.stdin.readline())

node = {}
for i in range(1, N + 1):
    node[i] = []

for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    node[a].append(b)
    node[b].append(a)

def dfs(n):
    if 1 in node[n]:
        return True

    visited[n] = 1
    for i in node[n]:
        if visited[i] != 1:
            dfs(i)

for i in range(2, N + 1):
    if len(node[i]) == 1:
        print(node[i][0])
    elif 1 in node[i]:
        print(1)
    else:
        for k in node[i]:
            visited = [0] * (N + 1)
            visited[i] = 1
            if dfs(k):
                print(k)

 

해당 코드는 노드 오름차순으로 했을 때의 관점이다. 

좀 여러 조건들이 있다 ...

 

1. 1개 있는 경우 - 바로 출력

2. 1이 있는 경우 - 바로 출력

3. 방문 처리

 

답은 똑같이 나오는데, 좀 복잡하다...

또 쓸때 없는 반복문들 많아서 시간 초과가 뜬 것 같다 ㅠㅠ 

 

 

📌 문제 코멘트 

→ BFS나 DFS나 어떤 관점에서 보느냐가 중요한 것 같다.

만일에 각 노드별 오름차순으로 보는 경우 다소 복잡해진다. 

재귀를 파고파고 들어 여러 조건들을 만들어서 필터링을 해줘야한다. 

 

이 문제같은 경우 오름차순이 아니라, 트리 부모-자식순으로 타고타고 가야된다.

특히 트리 문제 같은 경우는 , 트리 부모-자식순으로 타는 관점이 좀 더 옳바른 것 같다

 

---

📚문제

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

입력

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

출력

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

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6