99클럽 코테 스터디 17일차 TIL / [백준] 사자와 토끼

오늘의 학습 키워드

---

이분그래프

문제

---

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

• 플랫폼: 백준
• 문제명: 사자와 토끼
• 난이도: 골드 1

풀이

---

import java.io.*;
import java.util.*;
public class Main {

    static boolean[] visited;
    static int[] colors;
    static ArrayList<Integer>[] nodes;
    static boolean isPossible = true;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        nodes = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        colors = new int[n + 1];

        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            nodes[u].add(v);
            nodes[v].add(u);
        }

        dfs(1, n);

        if (isPossible) {
            long cnt1 = 0;
            long cnt2 = 0;

            for (int i = 1; i <= n; i++) {
                if (colors[i] % 2 == 0) {
                    cnt1++;
                } else {
                    cnt2++;
                }
            }

            System.out.println(cnt1 * cnt2 * 2);
        } else {
            System.out.println(0);
        }
    }

    public static void dfs(int node, int n) {
        if (!isPossible) {
            return ;
        }

        visited[node] = true;

        for (Integer nextNode : nodes[node]) {
            if (!visited[nextNode]) {
                colors[nextNode] = (colors[node] + 1) % 2;
                dfs(nextNode, n);
            } else {
                if (colors[node] == colors[nextNode]) {
                    isPossible = false;
                    return ;
                }
            }
        }
    }
}

접근

• 처음에는 수풀 사이의 거리가 홀수일 때 게임이 끝나지 않는 케이스가 된다는 아이디어를 기반으로 구현을 시도했습니다.
  • 인접행렬을 만들어서 직접 거리를 구하려고 했는데, 입력 조건이 수풀의 수 N(2 ≤ N ≤ 50,000), 오솔길의 수 M(1 ≤ M ≤ 500,000)로 1초 이내 풀이가 불가능하다고 판단했습니다.
• 그 다음 접근했던 것이 이분그래프입니다. 인접한 노드들을 서로 다른 색상으로 칠할 수 있다면 이분그래프이고, 이분그래프라면 서로 다른 색상에서 시작할 경우 영원히 게임이 끝나지 않게 됩니다.
  • 구현
    1. 이분그래프인지 확인 → DFS
       • DFS로 노드를 탐색하며 colors 배열에 서로 다른 색상을 칠합니다.
       • 만약 방문했던 노드라면 colors 값을 비교하여 같다면 이분그래프가 될 수 없는 것이므로 isPossible 변수 값을 false로 바꾸고 종료합니다.
    2. 맞다면 경우의 수 계산
       • 배치할 수 있는 경우의 수: A 색상 개수 x B 색상 개수 x 2

소요 시간

2시간