IT 개발 돼지의 일상

출처 : https://www.acmicpc.net/problem/1953 "연결 요소들을 탐색해! 아이디어가 필요한 BFS" 해당 문제와 같이 이분( 팀을 나누거나, 선택/비선택 등 ) 하는 문제는 주로 비트마스크를 사용했다. 하지만 비트마스크는 비트 연산이므로 N이 32자리를 넘어서는 수에 대해서는 사용하지 못한다. 해당 문제의 경우 n이 최대 100이므로 비트마스크를 사용하지 못한다. 그렇다면 탐색을 통해 팀을 나누어 주어야 한다. 팀이 될 수 있는 경우로 모든 경로를 탐색한다면 오래 걸릴 듯 했다. 따라서 1번 노드를 시작으로 같은 팀이 절대 될 수 없는 것들을 먼저 분류 했다. 풀다 보니, 연결 요소의 개수를 탐색하는 것과 비슷했다. 1번 노드 부터 서로 싫어하는 노드들의 연결 요소를 따라 탐색..