99 클럽 코테 스터디 17일차 TIL + 백준 17834 사자와 토끼 완벽 설명!

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: 이분 그래프

이분 그래프에 대해서 알지 못하면 풀 수 없는 문제였다. 나는 몰라서, 먼저 이분 그래프를 공부한 뒤에 다시 문제를 접했다. 먼저 이분 그래프에 대한 설명부터 적으려고 하는데, 이에 대해서 아시는 분들은 목차에서 (3) 풀이 방식 부터 보시길 바란다.

(1) 이분 그래프란 무엇인가요?

그래프의 정점들을 2개의 부분집합으로 분할 했을 때, 정점이

1. 같은 부분집합 내의 정점과는 간선을 가지지 않는다.
2. 무조건 반대편 부분집합이랑만 간선을 가진다.

가 성립하면, 해당 그래프를 이분 그래프라고 한다. 말로 하니까 어려운데, 그림으로 그려보겠다.

다음과 같이 생긴 그래프가 있다. 해당 그래프는 이분 그래프이다. 이분 그래프 임을 증명하는 2개의 부분집합으로 나누어 보면, 다음과 같다.

만약 그래프가 다음과 같이 바뀌면,

이분 그래프의 2개의 조건을 맞추기 위해서는 부분집합이 3개가 필요해진다. 따라서 이는 2개의 부분집합으로 나누어야 한다는 이분 그래프의 첫 번째 조건을 지키지 못해서, 더 이상 이분 그래프가 아니게 된다.

다음과 같이 외딴 섬이 있는 경우라면 어떻게 될까?

당연히 이분 그래프이다. 이때는 G,H가 양 부분집합 중 어디에 들어가든, 각자 따로따로 들어가면 성립한다.

(2) 이분 그래프 판단은 어떻게 하나요?

나는 BFS를 써서 그래프의 이분 그래프인지 여부를 판단했다. 판단 방법은 간단하다. 이분 그래프는 2개의 부분집합으로 완벽히 나눠져야 하기 때문에, 그래프 내의 모든 정점이 인접한 정점과는 다른 색이면서, 색깔이 2개만 쓰인다. 를 만족하면 이분 그래프이다.

a. 색깔을 2개 정해놓고, BFS를 통해, 인접한 정점에는 자신과 다른 색깔을 칠한다.
b. 만약 칠해져 있는 경우, 인접 정점의 색깔이 현 정점과 같으면 이분 그래프가 아니므로 바로 bfs를 종료한다.
c. 인접 정점과 현 정점의 색깔이 다르면, 이분 그래프인지 여부 확인을 계속해나간다.

(3) 풀이 방식

드디어 풀이 방식이다.
a. 이분 그래프인지 판단한다. 만약 이분 그래프가 맞다면, 색깔별로 정점이 몇 개 있는지 고른다.
b. 부분집합을 A와 B라고 할 때, A에 토끼, B에 사자 혹은 B에 사자, A에 토끼 라는 경우만 만족하면, 게임을 절대 끝낼 수 없는 경우다. 무조건 움직여야 하기에, 각자 서로 다른 부분집합으로 영원히 이동할 것이기 때문이다.
c. 따라서 A 부분집합의 원소 개수 x B의 부분집합의 원소 개수 X 2 (토끼 사자 위치 체인지)가 답이 된다.

3. 코드 분석

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

public class Main {
    // 인접 리스트
    static ArrayList<Integer> [] lists;
    static char [] vertex_color;
    static char [] color = new char[]{'B','W'};
    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());
        lists = new ArrayList[N+1];
        vertex_color = new char[N+1];
        for (int i = 1; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start   = Integer.parseInt(st.nextToken());
            int end     = Integer.parseInt(st.nextToken());
            lists[start].add(end);
            lists[end].add(start);
        }

        if (!bfs(1)) {
            System.out.println(0);
        }else {
            int cnt = 0;
            int Bcnt = 0;
            int Wcnt = 0;
            for (int i = 1; i < vertex_color.length; i++) {
                if(vertex_color[i] == 'B') Bcnt++;
                else Wcnt++;
            }
            cnt += Bcnt*Wcnt*2;
            System.out.println(cnt);
        }
    }
    // 현 위치에서 색깔 칠하기 -> 해당 문제는 모든 정점이 이어져 있으므로, BFS 딱 한 번 하면 된다. 
    public static boolean bfs(int start) {
        int value = 0;
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();
        aq1.add(start);
        vertex_color[start] = color[toggle(value)];

        while (!aq1.isEmpty()){
            int Qsize = aq1.size();
            value++;
            for (int i = 0; i < Qsize; i++) {
                int now = aq1.poll();
                for (int j = 0; j < lists[now].size(); j++) {
                    int next = lists[now].get(j);
                    if(vertex_color[next] == '\u0000') {
                        vertex_color[next] = color[toggle(value)];
                        aq1.add(next);
                    }else if(vertex_color[next] == vertex_color[now]) return false;

                }
            }
        }
        return true;
    }
    // 색깔 토글 함수
    public static int toggle (int value) {
        return value%2;
    }
}