본문 바로가기

PS/백준

[BOJ] 백준 11725 트리의 부모 찾기 (Swift)

반응형

문제

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

 

11725번: 트리의 부모 찾기

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

www.acmicpc.net

풀이

image

  • 먼저 트리를 그려보았음
  • 루트노드가 1로 고정되어 있어서 BFS/DFS를 1에서 한번만 수행시키면 되겠다고 생각했음
  • 간선의 개수는 노드의 개수 - 1개 이므로, 무조건 모든 노드가 연결되어 있을 것이라고 생각했음
  • 부모의 노드를 알기 위해서는 현재노드 -> 다음노드 로 탐색할 때, 현재노드의 번호를 어딘가에 담아둬야 될 것이라고 생각했음
  • visited 배열을 [Bool] 자료형으로 선언해서 사용했었는데, [Int]로 선언에서 그곳에 담아두어서 해결할 수 있다고 아이디어를 떠올렸음

소스코드

후기

부모의 노드 번호를 어떻게 알 수 있을까하고 생각을 좀 해봤던 것 같다.
맨 처음에는 외부로 배열을 선언하여 노드의 번호를 인덱스로 이전 노드의 번호를 넣어줄 까 했었는데,
visited 배열을 [Int]로 선언하여 해결할 수 있겠다는 아이디어를 떠올렸다.
생각한대로 풀이해서 좋았다!! 🙌

반응형