BOJ 11725 트리의 부모 찾기 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

루트 없는 트리가 주어짐.

트리의 루트를 1이라고 가정할때, 각 노드의 부모를 구하는 프로그램 작성

두 번째 단계 (문제 핵심 파악)

무방향 비순환 그래프임을 깨달았다.

이는 트리 이며, 트리 순회 알고리즘(DFS, BFS)을 떠올렸다.

• 입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어짐.

둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

• 출력

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

이때 노드의 개수가 십만까지 가능하므로, 재귀를 이용한 DFS 풀이는 살짝 불리하다고 생각.

따라서 BFS로 풀이하겠음.

• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다

코드 작성

from collections import deque

n = int(input())
visited = [False for _ in range(n + 1)]  # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
answer = [0 for _ in range(n + 1)]  # 정답 담을 리스트
graph = [[0] for _ in range(n + 1)]  # 트리

for _ in range(n - 1):  # 1은 제외
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)  # 무방향은 양방향임.

def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    que = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌때까지 반복
    while que:
        v = que.popleft()
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                answer[i] = v
                que.append(i)
                visited[i] = True

bfs(graph, 1, visited)

for i in range(2, n + 1):  # 2번 노드부터 시행
    print(answer[i])

느낀점

이코테 3회독 다시 가야하나..