[Algorithm] [Python&Swift] BOJ/백준 - 5567 _ 결혼식

5567 - 결혼식

 

문제

---

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

 

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

 

출력

---

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

 

제출코드

---

Swift

 

Python

 

문제풀이

---

그래프 탐색을 이용하면 간단하게 풀어낼 수 있는 문제입니다.

 

결론적으로 상근이는 자신의 친구와 자신의 친구의 친구까지 결혼식에 초대합니다.

 

주어지는 친구 리스트를 1 상근이 자기 자신을 루트 노드로 갖는 트리로 빗대어 생각해보면 level 1 은 자기 자신인 상근이를 의미할 것이며 level 2는 상근이의 친구들을 의미하며 level 3은 상근이의 친구의 친구들이 위치합니다.

 

트리의 level 을 3까지 탐색을 진행한다는 의미입니다.

 

즉, 루트노드를 제외하고서 간선을 2개 거쳐서까지 도달할 수 있는 노드, depth 가 2인 노드들을 탐색합니다.

 

위 아이디어를 코드로 구현하여 문제를 풀었습니다.