[자바] 백준 1953 - 팀배분 (java)

목차

문제 : boj1953

 

 

필요 알고리즘

• 이분 그래프 (bipartite graph), 그래프 탐색 (BFS, DFS 등)
  
  • 이분 그래프에 대한 개념이 있다면 좀 더 쉽게 풀 수 있는 그래프 탐색 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  2년전에 못 푼 기록이 있어 풀어봤다. 별 어려움 없이 바로 푼걸 보면 발전은 있었나보다. 2년전엔 HashSet을 사용해 넣을 때 마다 겹치는게 있는지 검색해본 것 같다. 이런방식으론 당연히 풀기 어려웠을 것 같다.

 

  이번에 문제의 경우 풀이는 지문의 "팀을 나누는 것이 불가능 한 경우는 없다고 하자." 라는 부분을 보고 떠올랐다. 이 말은 서로 싫어하는 사람들끼리 간선을 연결해 그래프로 나타냈을 때, 아래와 같은 경우는 입력되지 않는다는 얘기이다. (1과 2가 서로 싫어하고, 2와 3이 싫어하고, 3과 1이 서로 싫어하면 팀을 2개로 나누는 것이 불가하다.)

 

  즉, 알고리즘으로 얘기해보자면, "주어진 입력값은 반드시 이분 그래프"라는 말이다. 이분 그래프가 무엇인지 모른다면 '이분 그래프 (bitartite graph)' 글을 확인해보자. 그럼 이 문제는 "이분 그래프가 주어진다. 정점을 두 개의 집합으로 나눠라" 라는 문제가 되며, 이건 이하의 로직으로 풀 수 있다.

1. 아직 방문하지 않은 정점을 아무데나 방문한다.

2. 해당 정점을 둘 중 아무 팀에나 넣는다.

3. 인접한 정점을 방문한다. 이 때, 인접한 정점끼리는 서로 다른 팀에 넣는다.

4. '3'을 반복하다가, 인접한 곳이 없다면 '1'로 다시 돌아간다. 방문한 정점이 없어질때까지 계속하면 된다.

 

 

  예를들어 예제 입력 1을 그래프로 나타내보면 다음과 같다.

 

 

- 우선 아직 방문하지 않은 곳을 아무 곳이나 방문한다. '1'을 방문하겠다. 그리고 아무 팀이나 넣는다. 청팀에 넣어도 되고, 백팀에 넣어도 된다.

 

 

- '1'과 인접한 정점을 방문한다. '1'이랑 다른 팀에다 넣으면 된다.

 

 

- '3'과 인접한 정점을 방문한다. 역시 '3'이랑 다른 팀에만 넣으면 된다.

 

 

- 이제 다시 방문하지 않은 곳 중에 아무 곳이나 방문한다. 이번엔 '5'를 방문해보자. 역시 아무 팀에나 넣으면 되며, 이번엔 백팀에 넣어보겠다.

 

 

- '5'랑 인접한 정점을 방문하고, '5'랑 다른 팀에 넣으면 된다.

 

 

- 최종적으로 나뉜 두 팀을 정렬 후 출력하면 된다. 또, 위에서 얘기했던 로직에만 맞으면, 어떤 팀으로 나누는지는 상관 없다. 즉, 아래처럼 나누어도 이것도 답이다. 

 

 

  위의 과정을 반복해주면 되며, 위의 방법이 통하지 않는 경우가 있다면 문제 입력값이 잘못된 경우이므로 생각하지 않아도 된다.

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<Integer>[] edges = new List[n+1];
        for (int i = 1; i <= n; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            while (cnt-->0) {
                int cur = Integer.parseInt(st.nextToken());
                edges[i].add(cur);
                edges[cur].add(i);
            }
        }

        List<Integer> team1 = new ArrayList<>();
        List<Integer> team2 = new ArrayList<>();

        int[] v = new int[n+1];
        for (int i = 1; i <= n; i++) {
            if (v[i] != 0) continue;
            v[i] = 1;
            team1.add(i);

            Queue<Integer> q = new ArrayDeque<>();
            q.add(i);
            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int next : edges[cur]) {
                    if (v[next] != 0) continue;

                    if ((v[next] = 3-v[cur])==1) team1.add(next);
                    else team2.add(next);

                    q.add(next);
                }
            }
        }

        if (team2.isEmpty()) {
            team1.remove(0);
            team2.add(1);
        }

        Collections.sort(team1);
        Collections.sort(team2);

        StringBuilder sb = new StringBuilder();
        sb.append(team1.size()).append('\n');
        for (int cur : team1) {
            sb.append(cur).append(' ');
        }
        sb.append('\n');
        sb.append(team2.size()).append('\n');
        for (int cur : team2) {
            sb.append(cur).append(' ');
        }
        System.out.println(sb);
    }
}