백준_11725 (트리의 부모 찾기_DFS_자식과 부모 찾는 방법)

• 링크

---

메모한 것

루트는 레벨 1
부모를 구하자

input = edges

루트가 1이라고 가정했을 때의 부모를 출력-> 위로가는 dfs???

일단 연결해서 그래프부터 만들어보고 생각하자

알고리즘 -> 방식은 맞는데 더 좋은 방법이 밑에 있음

child = [[0] * n+1]를 만들고 .index()활용

1부터 bfs하는데
기본 bfs 뼈대에 노드 방문할 때마다 child[n].append(다음노드 전부) 똑같이 해주고
bfs 끝나면
for i in range(2, len(child)):
print(child[child[i]의 인덱스])

---

솔루션 코드 - 내가 푼

• 거의 한시간~한시간 반을 소비한듯...
• bfs까지는 금방해서 parent에 대한 자식은 금방 구했는데
• 그걸 역으로 바꾼 후 출력하는 과정에서 시간을 너무 많이 씀
• 특히 parent 배열이 "[[ ], [ ], [4], [1], [3]]" 형태로 되어있었는데
  • 출력하면 "[ ][ ] [4][1] [3]" 으로 나와서 바보같이 해멤...
  • 무엇보다 노드 인덱스가 한 자리 수만 있는게 아닌데 그거도 실수했음ㅋ;;;

from collections import deque
import sys
input = sys.stdin.readline

def bfs(check, graph, start,n):
    child = [[] for _ in range(n+1)]
    
    que = deque([start])
    check[start] = True
    
    while que:
        v = que.popleft()
        
        for i in graph[v]:
            if not check[i]:
                que.append(i)
                child[v].append(i)   # 부모에 대한 자식 넣기
                check[i] = True
                
    return child
    
n = int(input())
graph = [[] for _ in range(n+1)]
check = [False] * (n+1)

# 그래프 생성
for _ in range(n-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
# 부모에 대한 자식을 찾았음
child = bfs(check, graph, 1,n)       

# 역으로 바꾸기 (자식의 부모 인덱스 반환)
parent = [[] for _ in range(n+1)]

for i in range(1, len(child)):
    for j in child[i]:
        parent[j].append(i)
        
# 출력 - (중요...!!!!!!)
for i in range(len(parent)):
    if parent[i]:
        print(*list(map(int,parent[i])))

• 그 흔적...
  

---

솔루션 코드 - 블로그

• 이렇게 쉬운 방법이 있는데 괜히 꼬아서 생각함
• DFS 돌리면서 부모에 대한 자식을 방문하는데
  • 자식 방문하기 전에 자식배열 해당 인덱스에 부모값 저장

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

n = int(input())
tree = [[] for _ in range(n+1)]
par = [-1]*(n+1)            # (중요) 부모를 저장하는 자식 배열

# 그래프 생성 - 나와 동일
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

# DFS로 
def dfs(n):
    for i in tree[n]:       # (중요) 현 상태(=부모)의 자식들 꺼내서
        if par[i] == -1:    # (중요) 자식을 방문 안했으면
            par[i] = n      # (중요) 자식을 방문처리(= 부모 넣어준다)
            dfs(i)          # (중요) 자식의 부모찾기 수행
            
dfs(1)
for i in range(2,n+1):
    print(par[i])