[BOJ] 13265 색칠하기

문제

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

13265번: 색칠하기

 

 

접근

• 예제를 그래프로 그려서 확인해 보자.

• 각 노드를 R, G로 색칠해야 한다고 하자.
• 1번을 R로 색칠하면 문제의 조건에 의해 2, 3이 G로 색칠되어야 한다.
• 그런데 2번과 3번도 연결되어 있으므로 서로 다른 색이 되어야 하는데 G로 동일하므로 해당 그림은 두 가지 색으로 색칠할 수 없다.
• 이를 확인하는 방법은 BFS를 사용하여 구현할 수 있다. 시작 노드를 하나의 색으로 정해 칠한 뒤, 자신과 인접한 노드들을 자신과 다른 색으로 칠한다.
  • 이때 이미 색칠된 노드가 존재한다면 자신의 색과 다른지를 검사한다. 만약 같다면 문제의 조건에 맞게 2가지 색으로 칠할 수 없다는 것이기 때문에 false를 반환한다.
• 이때 1번 노드에는 어떠한 선도 연결되어 있지 않으나 다른 노드에 선이 연결될 수 있기 때문에 모든 노드에 대해 BFS를 실시해 판단해야 한다.

 

 

구현 코드

import java.util.*;
import java.io.*;

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    static int[] color;
    static int V;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < N; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            graph = new ArrayList<>();

            for (int i = 0; i <= V; i++){
                graph.add(new ArrayList<>());
            }

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

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph.get(a).add(b);
                graph.get(b).add(a);
            }

            boolean flag = true;
            for (int i = 1; i <= N; i++){
                flag = bfs(i);

                if (!flag){
                    break;
                }
            }

            if (flag){
                System.out.println("possible");
            } else {
                System.out.println("impossible");
            }
        }
    }

    public static boolean bfs(int startNode){
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(startNode);

        visited = new boolean[V + 1];
        color = new int[V + 1];

        visited[startNode] = true;
        color[startNode] = 1;

        while(!queue.isEmpty()){
            int cur = queue.pollFirst();

            for (int i = 0; i < graph.get(cur).size(); i++){
                int adjNode = graph.get(cur).get(i);

                if (visited[adjNode]){
                    if (color[adjNode] == color[cur]){
                        return false;
                    }

                    continue;
                }

                visited[adjNode] = true;
                if (color[cur] == 1){
                    color[adjNode] = 2;
                } else {
                    color[adjNode] = 1;
                }
                queue.addLast(adjNode);
            }
        }

        return true;
    }
}