[백준]13265: 색칠하기(java)

https://www.acmicpc.net/problem/13265

13265번: 색칠하기

문제

어린 토니킴은 색칠공부를 좋아한다.

토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.

이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.

동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자.

입력

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

그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n(1 ≤ n ≤ 1000)과 직선들의 개수 m(1 ≤ m ≤ 100,000)이 주어지고, 그 다음 줄부터 m 줄에 걸쳐 동그라미들이 연결된 직선에 대한 정보가 주어진다. (x y)로 주어지면 동그라미 x와 동그라미 y가 직선으로 서로 연결되었다는 의미이다. 동그라미들의 번호는 1 부터 n 까지이다.

출력

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

예제 입력 1 

3
4 5
1 2
2 3
3 4
1 3
2 4
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
8 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

예제 출력 1 

impossible
possible
possible

---

 

전체코드

package 백준;

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

public class BJ_G5_13265_색칠하기 {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static int[] color;
    static boolean isPossible = true;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder ans = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());

        for(int t=1; t<=TC; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            color = new int[N+1];
            graph = new ArrayList[N+1];
            isPossible = true;

            for(int i=1; i<=N; i++) {
                graph[i] = new ArrayList<>();
            }

            for(int i=0; i<M; i++) {
                st = new StringTokenizer(br.readLine());

                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());

                graph[s].add(e);
                graph[e].add(s);
            }

            for(int i=1; i<=N; i++) {
                if(!isPossible) break;
                if(color[i] == 0) {
                    color[i] = 1;
                    setColor(i);
                }
            }

            ans.append(isPossible? "possible" : "impossible");
            ans.append(t!=TC ? "\n" : "");
        }
        System.out.printf("%s", ans.toString());
    }

    public static void setColor(int node) {
        if(!isPossible) return;

        for(int i=0; i<graph[node].size(); i++) {
            int nextNode = graph[node].get(i);
            if(color[nextNode] == 0) {
                color[nextNode] = 3 - color[node];
                setColor(nextNode);
            }
            if(color[nextNode] == color[node]) {
                isPossible = false;
                return;
            }
        }
    }
}