[백준 - 9466] 텀 프로젝트 - C++

분류: BFS /

 

문제

문제 링크

문제 설명

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s₁, s₂, ..., s_r)이라 할 때, r=1이고 s₁이 s₁을 선택하는 경우나, s₁이 s₂를 선택하고, s₂가 s₃를 선택하고,..., s_r-1이 s_r을 선택하고, s_r이 s₁을 선택하는 경우에만 한 팀이 될 수 있다.

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 

풀이

- (기본) 케이스 분류

#include <iostream>
using namespace std;

enum Status { NOT_VISITED, VISITED, NOT_CYCLE, CYCLE };
int n; 
int nxt[100001];
Status status[100001];

// 지나온 길을 s로 마킹
void marking(int cur, Status s) {
    while(status[cur] == VISITED) {
        status[cur] = s;
        cur = nxt[cur];
    }
}

void run(int x) {
    int cur = x;
    while(true) {
        status[cur] = VISITED;
        cur = nxt[cur];
        // case 1, 2: 지나온 길 모두 사이클 아니다.
        if(status[cur] == CYCLE || status[cur] == NOT_CYCLE) {
            marking(x, NOT_CYCLE);
            return;
        }
        // case 3, 4: 지나온 길을 다시 만난 경우.
        if(status[cur] == VISITED) {
            // case 2, 3: (x에서 x) or (y에서 y)는 사이클이다.
            marking(cur, CYCLE);
            
            // case 3: x에서 y는 사이클이 아니다.
            if(cur != x) marking(x, NOT_CYCLE);
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--) {
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> nxt[i];
            status[i] = NOT_VISITED;
        }

        for(int i=1; i<=n; i++)
            if(status[i] == NOT_VISITED)
                run(i);
        
        int ans = 0;
        for(int i=1; i<=n; i++)
            if(status[i] == NOT_CYCLE) ans++;
        cout << ans << '\n';
    }
}

모든 노드는 `VISITED`, `NOT_VISITED`, `CYCLE`, `NOT_CYCLE`의 상태를 갖는 다고 하자.

• `VISITED`: `x`가 현재 지나온 길
• `NOT_CYCLE`: 아직 한번도 방문하지 않은 노드
• `CYCLE`: 사이클임이 확실한 노드
• `NOT_CYCLE`: 사이클이 아님이 확실 한 노드

전체적인 알고리즘은 아래와 같다.

• `NOT_VISITED`인 노드를 방문하며 `VISITED`로 현재 지나온 길을 마킹한다.
• `VISITED`를 만났다면 사이클이 있다.
• 사이클이 있다면 지나온 길은 `CYCLE` 혹은 `NOT_CYCLE`중 하나이다.

 

사이클을 찾는 것은 쉽다. 사이클을 만났을 때 지나온 길을 `CYCLE`혹은 `NOT_CYCLE`로 마킹하는 방법을 풀어쓰면 다음과같다.

`x`에서 유한한 linked list를 타고 진행 할 경우 발생할 수 있는 경우의 수는 4가지로 분류할 수 있다.

• case 1: 사이클인 노드(`CYCLE`)를 만난 경우
  • 이 경우 `x`에서 사이클 까지는 사이클이 아니다.(`NOT_CYCLE`)
• case 2: 사이클이 아닌 노드(`NOT_CYCLE`)를 만난 경우
  • 이 경우 `x`에서 사이클 까지는 사이클이 아니다.(`NOT_CYCLE`)
• case 3: 시작점(`x`)을 만나는 경우(`VISITED`)
  • 이 경우 `x`가 지나온 길은 모두 사이클이다.(`CYCLE`)
• case 4: 시작점(`x`)이 아닌 지나온 길(`VISITED`)을 만나는 경우. (이때 만난 노드를 `y`라 하자)
  • `x`에서 `y`까지는 사이클이 아니다.(`NOT_CYCLE`)
  • `y`에서 `y`까지는 사이클이다.(`CYCLE`) (`y`를 시작으로 하는 case 3과 같다.)

 

- visted 값을 다르게 하기

#include <iostream>
using namespace std;

int n; 
int nxt[100001];
int status[100001];
const int NOT_VISITED = 0, CYCLE = -1;

void run(int x) {
    int cur = x;
    while(true) {
        status[cur] = x;
        cur = nxt[cur];
        if(status[cur] == x) {
            while(status[cur] != CYCLE) {
                status[cur] = CYCLE;
                cur = nxt[cur];
            }
            return;
        }
        else if(status[cur] != NOT_VISITED) return;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while(T--) {
        cin >> n;
        for(int i=1; i<=n; i++){
            cin >> nxt[i];
            status[i] = NOT_VISITED;
        }

        for(int i=1; i<=n; i++)
            if(status[i] == NOT_VISITED)
                run(i);
        
        int ans = 0;
        for(int i=1; i<=n; i++)
            if(status[i] != CYCLE) ans++;
        cout << ans << '\n';
    }
}

`VISTED`를 시작 노드`x`의 값으로 마킹하고

`NOT_CYCLE`은 시작 노드값 `x`가 아닌 양수로 확인하면 위 풀이를 조금 더 간결하게 작성할 수 있다.

시작점이 여러개인 BFS를 진행할 때 visited 배열을 새로 만들거나 매번 초기화 시킬 경우 visited 배열의 값을 다르게해 체크할 수 있다.