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

오늘의 학습 키워드

   - 알고리즘

   - 그래프 탐색

   - 이분 그래프

공부한 내용 본인의 언어로 정리하기

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

그래프 탐색 문제를 풀었는데, 이분 그래프 개념이 들어가 있었다.

해당 개념을 몰라 찾아보고 다시 풀게 되었다.

 

이분 그래프란 쉽게말해 한 정점과 연결된 그래프의 색상이 빨강이고 하면,

빨간 정점과 연결된 모든 정점은 파랑색 정점이고, 파란 정점과 연결된 모든 정점은 빨간색 정점으로 이루어진 그래프이다.

 

그래서 예시로 주어진 그림을 표현하면 아래와 같이 이분 그래프가 성립한다.

 

하지만 3번 예시의 경우 아래와 같이 이분 그래프가 성립하지 않는다.

 

그래서 이분 그래프를 어떻게 이 문제에서 활용하냐면

만약 이분그래프가 성립된다면 사자와 토끼가 각각 빨강과 파랑 위치 또는 반대 위치에 있다면 절때 만날 수 없다.

(간선에서 만날 수는 있지만, 문제에서 이 경우 무시한다고 했다)

왜냐하면 이분 그래프 특성상 빨간색 정점에서는 파란색 정점으로, 파란색 정점에서는 빨간색 정점으로만 갈 수 있으므로 이론상 만날 수 없다는 것을 알 수 있다.

 

그리고 이분 그래프가 아니라면 문제의 조건인 어떻게 움직여도 영원히 게임이 끝나지 않는 초기 위치라는 조건을 만족할 수 없다.

 

풀이 과정은 다음과 같다.

1. 아무 정점에서나 색깔을 하나 지정하고 BFS 로직을 수행한다.

2. BFS를 통해 다음 정점으로 간다면, 해당 정점은 출발했던 색깔의 반대 색깔을 넣어준다.

2 - 1. 만약 다음 정점에서 이미 빨강이 칠해져 있는 상태이고, 파란색을 칠해야 하는 상황이라면

이는 예시 3번과 같이 이분 그래프가 아닌 예시이므로 0을 반환한다.

3. 이분 그래프를 만족했다면, 파란색과 빨간색 점에서 각각 1곳을 뽑는 경우의 수 이므로 이를 곱해준다.

3 - 1. 이 때 사자와 토끼의 위치는 반전될 수 있으므로 2를 더 곱해준다.

 

풀이는 다음과 같다.

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

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static ArrayList<Integer>[] graph;
    static int n, m;

    static int[] moveCnt, visit;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n + 1];
        visit = new int[n + 1];
        moveCnt = new int[n + 1];

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

        while (m-- > 0) {
            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);
        }

        ArrayDeque<int[]> que = new ArrayDeque<>();;

        boolean flag = true;
        int[] cnt = new int[3];

        visit[1] = 1;
        cnt[2]++;
        que.add(new int[] {1, 1});

        while(!que.isEmpty()) {

            int[] cur = que.pollFirst();
            int loc = cur[0];
            int color = cur[1];

            for (int next : graph[loc]) {
                if (visit[next] == 0) {
                    visit[next] = -color;
                    cnt[visit[next] + 1]++;
                    que.add(new int[] {next, -color});
                } else if (visit[next] == color) {
                    flag = false;
                    break;
                }
            }

            if (!flag) break;
        }

        int result = 0;
        if (flag) result = 2 * cnt[0] * cnt[2];
        System.out.println(result);

    }
}