[백준 19240] 장난감 동맹군 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/19240

19240번: 장난감 동맹군

 

문제

당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사이가 안 좋을 수 있는데 (가령 강아지 장난감과 고양이 장난감 혹은 배트맨과 조커) 그러한 장난감 쌍은 같은 동맹군에 속할 수 없다.

예를 들어, N = 3 이고 (1, 2)가 서로 동맹이 될 수 없고, (2, 3)도 서로 동맹이 될 수 없으며, (3, 1)도 서로 동맹이 될 수 없다고 해보자. 이 경우 어떻게 세 개의 장난감을 두 동맹군으로 나누더라도 두 동맹군 중 하나는 동맹이 될 수 없는 관계인 장난감 쌍을 가지게 되므로 나누는 것이 불가능하다. 다른 예로 N = 4 이고 (1, 2), (2, 3), (3, 4), (4, 1) 이렇게 네 쌍의 장난감 관계들이 주어진다면 {1, 3} 과 {2, 4} 두 동맹군으로 나눌 수 있다.

이렇게 다양한 이유로 서로 "동맹"이 될 수 없는 장난감 쌍이 총 M개 주어졌을 때, 당신은 N개의 장난감을 두 개의 동맹군으로 나누되 서로 동맹이 될 수 없는 장난감 쌍은 서로 다른 동맹군에 속하도록 나누고 싶다.

 

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 N과 M이 공백으로 구분되어 주어진다.

다음 M줄에 걸쳐 각 줄에 한 쌍의 장난감 번호가 공백으로 구분되어 주어진다.

 

출력

각 테스트 케이스에 대해 N개의 장난감을 두 동맹군으로 나눌 수 있는 경우 "YES"를 출력하고 그렇지 않은 경우 "NO"를 출력한다. (모두 대문자이며 따옴표는 제외)

풀이

접근법

1. 같은 동맹군에 속하지 않으려면 연결할 때 반대편에 연결하면 된다.
2. 만약 체크하면서 다른 동맹군이여야 하지만 같은 동맹군에 이미 속해있는 경우에만 NO
3. 나머지는 YES

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int[] group = new int[300010];
        test: for(int tc=1;tc<=T;tc++) {
            st = new StringTokenizer(br.readLine());
            int N=Integer.parseInt(st.nextToken());
            int M=Integer.parseInt(st.nextToken());
            List<Integer>[] list = new List[N+1];
            Arrays.fill(group, -1);
            // 1. 같은 동맹군에 속하지 않으려면 연결할 때 반대편에 연결하면 된다.
            for(int i=0;i<=N;i++) list[i] = new ArrayList<>();
            for(int i=0;i<M;i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                list[x].add(y);
                list[y].add(x);
            }
            Queue<Integer> queue = new LinkedList<>();
            for(int i=1;i<=N;i++) {
                if (group[i] != -1) continue;
                queue.clear();
                queue.add(i);
                group[i] = 0;
                while(!queue.isEmpty()) {
                    int now = queue.poll();
                    for(int x : list[now]) {
                        if (group[x] == -1) {
                            group[x] = (group[now] + 1) % 2;
                            queue.add(x);
                        } 
                        // 2. 만약 체크하면서 다른 동맹군이여야 하지만 같은 동맹군에 이미 속해있는 경우에만 NO
                        else if (group[x] == group[now]) {
                            sb.append("NO\n");
                            continue test;
                        }
                    }
                }
            }
            // 3. 나머지는 YES
            sb.append("YES\n");
        }
        System.out.println(sb);
    }
}

 

 

약 14분 정도 걸렸다.