11725번 '트리의 부모 찾기'

 

 

Java

 

ArrayList 의 배열을 생성해 주고, 배열의 각 요소에 대해서도 ArrayList 를 초기화해주어야 한다.

ArrayList 의 인덱스는 시작 정점을 나타내고, 그 요소의 ArrayList 의 요소는 시작 정점과 연결되어 있는 정점을 나타낸다.

---

 

Swift

 

[[Int]] 형의 배열을 생성하고, 인덱스로 접근하기 위해 repeating 할 수 있는 생성자를 이용하여 초기화한다.

Java 로 풀 때처럼 그래프를 저장한다.

---

 

BFS

 

1. 시작 정점에 대하여 탐색되었다고 체크하고, 그 정점을 Enqueue 한다.

2. 큐가 빌 때까지 다음의 과정을 반복한다.

   1. 큐의 요소를 Dequeue 한다.

   2. 그 요소와 이어져 있는 정점들을 순회하면서,

      1. 정점이 탐색된 상태가 아니라면, 탐색된 상태로 변경하고, 큐에 넣는다.
      2. 정점이 탐색된 상태라면 아무런 작업도 하지 않는다.