[백준]#1953 팀배분

문제

2007년 1월 9일(화)는 원장선생님의 말씀대로 어제와 같이 하루 일과를 팀플레이를 통해 하려고 한다. 이 날은 특별히 청팀과 백팀으로 두 팀을 나누어 팀전을 하려 한다. 하지만 어제 하루 팀플레이를 하면서, 서로 같은 팀을 하기 싫어하는 사람들이 생겼다.

이제 우리가 할 일은 다음과 같다. 사람들이 각각 싫어하는 사람들의 정보가 주어져 있을 때, 그 사람들의 요구를 수용하여 서로 싫어하는 사람은 같은 팀에 넣지 않으려 한다. 이 조건을 만족하여 n명의 사람들 두 팀으로 나누는 프로그램을 작성하여라.

입력

첫 줄에는 학생들의 수 n (1 ≤ n ≤ 100)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 서로가 싫어하는 사람들의 정보가 주어진다. i+1번째 줄에는 i번째 사람이 싫어하는 사람의 수와 싫어하는 사람들이 나온다.

모든 사람이 싫어하는 사람이 단 한 명도 없는 경우는 없다.

출력

첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속한 사람들을 출력한다. 단 답이 여러 가지 일 경우에는 한 가지만 출력하여도 좋다.

예제 입력 1

5
1 3
1 5
2 1 4
1 3
1 2

예제 출력 1

3
1 4 5
2
2 3

풀이

이 문제는 이분그래프 이론을 이용하면 풀 수 있었다. dfs(깊이 우선 탐색) 알고리즘을 이용해서 이분 그래프를 만들었어 답을 구했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.TreeSet;

public class Main {
    static TreeSet<Integer> white = new TreeSet<>();    //각 팀의 사람을 오름차순으로 정려하기 위해 treeset 사용
    static TreeSet<Integer> blue = new TreeSet<>();
    static ArrayList<Integer>[] map;
    static boolean[] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];
        map = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
            map[i] = new ArrayList<>();

        for(int i=1; i<=N; i++) {
            String[] input = br.readLine().split(" ");

            for(int j=1; j<input.length; j++) {
                map[i].add(Integer.parseInt(input[j]));
            }
        }

        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;    //팀 구성이 되지 않은 사람 팀 구성 시작
                white.add(i);
                dfs(i, 1);
            }
        }

        if(blue.isEmpty()) {        //싫어하는 사람이 없어서 모두 한팀으로 구성된 경우
            white.remove(1);
            blue.add(1);
        }

        StringBuilder sb = new StringBuilder();

        sb.append(blue.size()).append("\n");

        for(int x : blue)
            sb.append(x).append(" ");

        sb.append("\n");
        sb.append(white.size()).append("\n");

        for(int x : white)
            sb.append(x).append(" ");

        System.out.println(sb);
    }

    public static void dfs(int idx, int team) {   //idx의 사람을 싫어하는 사람은 반대 팀으로 설정

        if(team==1) {
            for(int next : map[idx]) {
                if(!visited[next]) {
                    visited[next] = true;
                    blue.add(next);
                    dfs(next, 0);
                }
            }
        }

        else {
            for(int next : map[idx]) {
                if(!visited[next]) {
                    visited[next] = true;
                    white.add(next);
                    dfs(next, 1);
                }
            }
        }
    }
}