백준 9466번 텀 프로젝트 :: 마이구미

이번 글은 백준 9466번 문제 "텀 프로젝트" 를 다뤄본다.

백준 알고리즘 문제 9466번 텀 프로젝트 

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

DFS, BFS 관련 글.

http://mygumi.tistory.com/102

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

문제를 보면 10451번과 흡사하다.

이 문제도 사이클을 찾으면 된다.

10451번과 다른 점은 중복 입력이 주어진다는 것이다.

그렇다는 건, 순열 그래프와 달리 그래프가 모든 정점에 연결되어있는 사이클이 존재하는 그래프가 아니라는 것이다.

위와 같이 입력이 주어졌을 경우를 들어보자.

위와 같이 결과는 {3}, {4,6,7} 팀이 이루어진다.

결국 팀을 이루어질 수 있는 경우는 2가지다.

1. 혼자 팀을 이룰 경우.

2 .여러 명이 팀을 이룰 경우.

public static void dfs(ArrayList<Integer>[] a, boolean[] c, int v) {

    if (c[v]) {
        return;
    }

    c[v] = true;

    for (int vv : a[v]) {

        if (!c[vv]) {
            dfs(a, c, vv);
        }

    }

}

위의 기본적인 dfs 탐색방식으로 돌려보자.

3과 같이 혼자 팀을 이룰 경우는 이전의 방문했기 때문에 사이클이라고 판단할 수 없게 된다.

그렇다고 방문여부를 체크하지 않는다면, {4,5,6} 그래프의 중복 여부를 판단할 수 없게 된다.

그렇기에 이렇게 생각해볼 수 있다.

하나의 그래프에 존재하는 모든 정점에 연결된 사이클이 존재하지 않을 수 있지만, 어쨌든 사이클은 존재한다.

이 점은 활용하면 된다.

탐색할수록 정점의 개수(cnt)는 늘어간다.

c 배열에 탐색할때마다 해당 정점을 기준으로 탐색된 정점의 개수를 저장한다.

그러던 중 사이클이 존재하면, 사이클이 존재하는 정점을 인덱스로 활용하는 것이다.

(탐색된 정점 개수 - 사이클 정점에 대한 길이)를 통해 사이클을 이루는 정점의 개수를 구하게 된다.

위 그림처럼 현재 정점을 1->5->3->4->2 경로를 통해 5번 탐색했다.

방문한 적이 있는 2 정점을 탐색시 2 정점은 c[2] 값은 2번째로 탐색되었기 때문에 2가 들어있다.

그리고 예외의 경우가 있다.

첫번째 그림처럼 2->1, 5->3 과 같은 경우를 위해 조건을 추가하면 된다.

step은 시작 정점이라고 보면 된다.

방문했고, 시작 정점이랑 다르다면 사이클이 아니기 때문에 s 배열과 step을 활용했다.

public static int dfs(int[] a, int[] c, int[] s, int v, int step) {
    int cnt = 1;

    while(true) {

        if (c[v] != 0) {
            if (s[v] != step) {
                // 이미 방문했고, 정점 시작점이 다를 경우 사이클 x
                return 0;
            }
            return cnt - c[v];
        }

        s[v] = step;
        c[v] = cnt;
        v = a[v];

        cnt += 1;
    }

}

본인 블로그 내 그래프 관련 글들이 더 존재한다.

참고하면 감사하겠다

백준 알고리즘 9466번 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/9466.java