
[Python] 친구 관계(DFS)
CS/알고리즘
2021. 6. 1. 10:06
문제 기술 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..