99클럽 코테 스터디 17일차 TIL [이분그래프, dfs]

- 오늘의 학습 키워드 : 이분그래프, dfs

[문제 이름 :   사자와 토끼(백준, G1) ]

문제 url : https://www.acmicpc.net/problem/17834

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] visited;
    static long count1, count2, totalPairs;
    static boolean isGraph; // 이분 그래프 여부

    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());

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }

        isGraph = true;
        totalPairs = 0;
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                count1 = 0;
                count2 = 0;
                visited[i] = 1;
                count1++;
                dfs(i);
                if (!isGraph) {
                    System.out.println(0);
                    return;
                }
                totalPairs += count1 * count2;
            }
        }

        System.out.println(2 * totalPairs);
    }

    static void dfs(int node) {
        for (int now : graph[node]) {
            if (visited[now] == 0) {
                visited[now] = (visited[node] == 1) ? 2 : 1;
                if (visited[now] == 1) count1++;
                else count2++;
                dfs(now);
            } else if (visited[now] == visited[node]) {
                isGraph = false;
                return;
            }
        }
    }
}

 

[풀이 과정]

1. 이분그래프와 DFS를 활용하여 문제에 접근한다.

2. 이분그래프이면서 서로 다른 색깔에서 토끼와 사자가 출발하게 된다면, 둘은 절대 만날일이 없으며, 각 색깔의 수 * 2 (=빨간색 4개 * 파란색 4개 * 2) 개의 경우의 수가 정답이 된다.

3. 이분그래프가 아니라면 0을 출력하고, 이분그래프라면 색깔의 개수 * 2로 토끼와 사자가 만나지 않는 경우의 수를 출력해준다.

4. 모든 수풀에 대해 DFS를 수행하며, 처음 수행 시 첫 번째 그룹으로 마킹한다. 아직 방문하지 않은 경우에는, 기존 노드와 방문하여 같은 그룹인지를 체크하여 now에 해당하는 그룹을 마킹한다.

5. 만약 같은 그룹을 발견한 경우, 이는 이분 그래프에 해당하지 않으므로 isGraph = false; 이후 0을 출력하게 된다.

 

문제 구상이 많이 어려웠다. 다른 사람의 블로그를 참고하여 문제의 아이디어를 얻었다.

풀이 시간 : 1시간 30분

 

내일은 백트래킹 개념을 학습하고, 관련 문제들을 풀어보려고 한다.

 

[참고] 

https://congsoony.tistory.com/12