백준 1953. 팀배분 :: 돼지개발자

출처 : https://www.acmicpc.net/problem/1953

"연결 요소들을 탐색해! 아이디어가 필요한 BFS"

해당 문제와 같이 이분( 팀을 나누거나, 선택/비선택 등 ) 하는 문제는 주로 비트마스크를 사용했다. 하지만 비트마스크는 비트 연산이므로 N이 32자리를 넘어서는 수에 대해서는 사용하지 못한다. 

해당 문제의 경우 n이 최대 100이므로 비트마스크를 사용하지 못한다. 그렇다면 탐색을 통해 팀을 나누어 주어야 한다.

팀이 될 수 있는 경우로 모든 경로를 탐색한다면 오래 걸릴 듯 했다. 따라서 1번 노드를 시작으로 같은 팀이 절대 될 수 없는 것들을 먼저 분류 했다. 풀다 보니, 연결 요소의 개수를 탐색하는 것과 비슷했다. 

1번 노드 부터 서로 싫어하는 노드들의 연결 요소를 따라 탐색하고 이 과정에서 노드들의 팀분류가 이루어진다.

이렇게 첫번째 연결 요소를 탐색하고 나면, 다른 연결 요소를 또 탐색한다. 이런 과정을 반복하면 모든 사람에 대해 팀분류가 이루어진다.

팀의 분류는 int 형 배열인 visited 를 가지고 1 과 -1 로 나누었다. 

예제 입력의 탐색 과정은 간단히 아래와 같다.

1 - 3 - 4

2 - 5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int[][] map;
    static int[] visited;
    static Queue<Integer> q = new LinkedList<>();
    static StringBuffer sb1 = new StringBuffer();
    static StringBuffer sb2 = new StringBuffer();
    static int b,w;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        map = new int[n+1][n+1];
        visited = new int[n+1];
        
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            int cnt = Integer.parseInt(st.nextToken());
            for (int j = 0; j < cnt; j++) {
                int man = Integer.parseInt(st.nextToken());
                map[i][man] = map[man][i] = 1;
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if(visited[i] != 0) continue;
            
            visited[i] = 1;
            q.add(i);
                
            while(!q.isEmpty()) {
                
                int cur = q.poll();
                
                for (int j = 1; j <= n; j++) {
                    
                    if(visited[j] != 0) continue;
                    
                    if(map[cur][j] == 1) {
                        visited[j] = visited[cur]*-1;
                        q.add(j);
                    }
                }
            }
            
        }
        
        for (int i = 1; i <= n; i++) {
            if(visited[i] == 1) {
                b++;
                sb1.append(i+" ");
            }
            else {
                w++;
                sb2.append(i+" ");
            }
        }
        
        System.out.println(b);
        System.out.println(sb1.toString());
        System.out.println(w);
        System.out.println(sb2.toString());
    }
}