[백준] 11725. 트리의 부모 찾기 (실버2, Python)

풀이

사실 문제를 이해 못해서 다른 블로그를 엄청 많이 봤다...!

예시1번에서 내가 생각한 정답은 '1 1 4 4 6 3' 이었는데 왜 '4 6 1 3 1 4'인지 이해가 안되서 한참 보았다.

 

블로그를 통해 문제를 이해하고 다시 문제를 보니 내가 놓친 부분이 보였다.

• 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력

노드 번호가 2번인 부모 노드부터 n번인 부모 노드 번호까지 출력하라는 의미인게 이제서야 보였다... ㅎ

 

 

 

먼저 제시된 예시1 트리를 표현했다

1. 각 노드와 연결된 노드를 저장

2. 연결되어 있는 노드를 방문하면서 각 부모 노드를 저장하면된다.

각 노드와 연결된 노드	각 노드의 부모 노드
노드, 1: 4, 6 노드, 2: 4, 7 노드, 3: 5, 6 노드, 4: 1, 2, 7 노드, 5: 3 노드, 6: 1, 3 노드, 7: 2, 4	노드, 2의 부모 노드 -> 노드, 4 노드, 3의 부모 노드 -> 노드, 6 노드, 4의 부모 노드 -> 노드, 1 노드, 5의 부모 노드 -> 노드, 3 노드, 6의 부모 노드 -> 노드, 1 노드, 7의 부모 노드 -> 노드, 4

 

 

treeList: 각 노드와 연결된 노드를 저장

childQueue: 현재 노드와 인접한 노드 모두

child: 현재 노드와 인접한 노드 중 하나

parent: 각 노드의 부모 노드 번호 저장 장소

 

루트 노드인 1은 무조건 수행하면서 인접 노드를 큐에 저장

저장된 큐를 기준으로 반복문 수행

아직 부모 노드를 저장하지 않은 노드를 저장 (단, 1번 노드는 빈칸으로 둘것)

def findParent():
    childQueue = queue.Queue()
    
    for c in treeList[1]:
        parent[c] = 1
        childQueue.put(c) 
    
    while childQueue.qsize() > 0:
        child = childQueue.get()
        for c in treeList[child]:
            if parent[c] == 0 and c != 1:
                parent[c] = child
                childQueue.put(c)
                
    print("\n".join(map(str, parent[2:])))

 

 

 

최종 코드

import queue

def findParent():
    childQueue = queue.Queue()
    
    for c in treeList[1]:
        parent[c] = 1
        childQueue.put(c) 
    
    while childQueue.qsize() > 0:
        child = childQueue.get()
        for c in treeList[child]:
            if parent[c] == 0 and c != 1:
                parent[c] = child
                childQueue.put(c)
                
    print("\n".join(map(str, parent[2:])))

n = int(input())

treeList = [[] for _ in range(n+1)]
parent = [0] * (n+1)

for i in range(n-1):
    a, b = map(int, input().split())
    treeList[a].append(b)
    treeList[b].append(a)

findParent()

 

 

 

 

백준 문제

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

 

GitHub

https://github.com/ujin302/CodingTest_2023/blob/main/Code/BackJun/silver/s2/s2_11725.py

CodingTest_2023/Code/BackJun/silver/s2/s2_11725.py at main · ujin302/CodingTest_2023