백준 13265 - 색칠하기

문제

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

리뷰

DFS나 BFS로 풀이할 수 있는 문제였다. 필자는 DFS로 풀이하였다.

문제의 조건에 따라 DFS를 통해 현재 탐색 중인 정점과 다른 색으로 다음에
탐색할 정점들을 색칠하는데, 만약 연결된 정점이 이미 같은 색으로 색칠된 경우
2가지 색상으로 색칠이 불가능한 경우이므로 answer 를 false로 갱신하고
탐색을 종료하여 답을 도출하도록 로직을 구성하였다.

유의할 점은 모든 동그라미들 사이에 직선이 있을 필요가 없다는 조건에서
모든 정점이 연결되어 있지 않을 수 있기 때문에, 개별 정점마다 DFS를 진행하며
분리되어 존재하는 그래프들을 전부 확인해주어야 한다는 점이었다.

로직의 시간복잡도는 정점마다 DFS 로직을 수행하는 루프 부분의 $O(n(n+m))=O(n^2)$으로
수렴하고 이는 $n=1,000$, $m=100,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] visited;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        int n, m, u, v;
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = parseInt(st.nextToken());
            m = parseInt(st.nextToken());

            graph.add(null);
            for (int i = 0; i < n; i++)
                graph.add(new ArrayList<>());

            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                u = parseInt(st.nextToken());
                v = parseInt(st.nextToken());

                graph.get(u).add(v);
                graph.get(v).add(u);
            }

            answer = true;
            visited = new int[n + 1];
            Arrays.fill(visited, -1);
            for (int current = 1; current < visited.length; current++)
                if (visited[current] == -1)
                    dfs(current, 0);

            sb.append(answer ? "possible" : "impossible").append("\n");

            graph.clear();
        }

        System.out.print(sb);
        br.close();
    }

    static void dfs(int current, int color) {
        visited[current] = color;

        for (Integer next : graph.get(current)) {
            if (visited[next] == color) {
                answer = false;
                return;
            }

            if (visited[next] == -1)
                dfs(next, (color + 1) % 2);
        }
    }
}

결과