[Python] 친구 관계(DFS)

문제 기술

0부터 n-1까지 번호가 붙여진 n명의 사람들의 친구관계가 주어져 있다. 다음은 6명의 사람들에 대한 친구관계를 보여준다.

친구관계로 연결되어 있는 집단의 개수와 가장 큰 집단의 크기 (사람 수), 가장 작은 집단의 크기를 구하는 프로그램을 작성하시오. 위의 그림에서 집단은 2개이고 가장 큰 집단은 {1, 2, 3, 5, 6}으로서 크기는 5이고 가장 작은 집단은 {0, 4}로서 크기는 2이이다. 

 

요구조건: 친구관계를 인접리스트로 표현하고, 탐색방법은 깊이우선탐색을 이용한다.

 

첫 번째 줄에 사람들의 수 n(1이상 1,000이하 정수)와 친구 관계 수 m(0 이상 300,000 이하 정수)가 주어진다. 다음 m개의 각 줄에 친구 관계를 나타내는 두 사람의 번호가 주어진다.

 

입력

7 6
1 2
1 5
5 6 
5 2
0 4
2 3

출력

2 
5 2

 

나의 코드

12행까지로 이중 리스트 형태의 인접 리스트를 만들었다.

16행의 dfs 함수부터 시작해보자면, n만큼의 범위를 도는 i의 값을 for문에서 dfs의 매개변수로 넣도록 했다.

첫 시작값을 스택에 넣었고, 스택이 있을 경우 pop해서 빼내준 뒤, 방문하지 않았을 경우에는 방문처리를 하고 people(연결되어 있는 사람 수)을 1 더해줬다. 그리고, 그 시작점 v의 인접리스트 내 값들을 전부 24, 25행을 통해 스택에 넣어줬다. 이런 방식으로 계속 진행을 하여 결국에 나오는 값은, visited 리스트(n개의 인덱스에 각각에 대해 방문여부를 체크)와 people 값이다.

people이 0이 아닐 경우, 즉 간선이 1개 이상 있는 경우에는 relationship이라는 새로운 변수의 값을 1 더해줬고, result라는 비어있는 배열에 이 people을 더해줬다. 

최종적으로 relationship에는 집단의 수, 그러니까 연결되어있는 작은 집단들의 수가 저장이 되겠고, result에는 각 집단의 크기가 들어가게 될 것이다.

코드는 여기에 있다.