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

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/9466

---

2. 풀이 과정

• 문제 해결의 흐름 
  • 백준 '2668 숫자고르기'와 비슷하다고 생각했는데 많이 다른 거 같다 ㅠㅠ...
  • 이 문제의 키포인트는 '사이클을 완성할 때까지 탐색하다가 사이클을 이루는 요소들 골라주기'이다. 
  •  사이클을 완성시키는 경우는 어떤 것이 있을까? 예를 들어 아래의 경우 1 -> 4 -> 7 -> 6 -> 4 와 같이 사이클을 형성한다. 1로 시작해서 4로 끝났는데 뭔 사이클이냐?라고 생각할 수도 있다. 하지만 4 -> 7 -> 6 -> 4의 사이클을 이룬다! 따라서 이와 같이 사이클을 이루는 경우 탐색을 멈추고 사이클을 이루는 숫자들을 백트래킹해주자! 

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

 

• 나의 코드 

#include <iostream>
#include <cstring>
#define MAX 100001

using namespace std;

int arrStudent[MAX];
bool visited[MAX]; // 방문 처리
bool done[MAX]; // 팀을 이미 구해서 더 이상 볼 일 없음
int result; // 팀에 속하는 사람들 구하기


void dfs(int current) {
    visited[current] = true;    // 방문 처리해주기 

    if (!visited[arrStudent[current]]) { // 방문한 적 없다면 
        dfs(arrStudent[current]);
    } else if (!done[arrStudent[current]]) { // 처음 보는 사이클이라면? 
        for (int i = arrStudent[current]; i != current; i = arrStudent[i]) { // 백트래킹 
            result += 1; 
        }
        result += 1; // 자기 자신도 세주기
    }

    done[current] = true;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int n;
        // 입력 받기
        cin >> n;
        for (int j = 1; j <= n; j++) {
            cin >> arrStudent[j];
        }

        // 초기화
        result = 0;
        memset(visited, false, sizeof(visited));
        memset(done, false, sizeof done);

        // dfs 실행
        for (int j = 1; j <= n; j++) {
            if (!visited[j]) {
                dfs(j);
            }
        }

        // 출력하기
        cout << n - result << endl;
    }

    return 0;
}

• 이 문제를 통해 얻어갈 수 있는 것들
  • 아래와 같은 반복문을 통해 배열 요소를 백트래킹할 수 있다.

// i가 current값이 아닐 때까지 요소를 역탐색하자! 
for (int i = arr[i]; i != current; i = arr[i]) {
}

 

---

3. 후기

 너무 어려워서 아래 블로그를 참고했다. dfs는 역시 쉽지 않다 ㅠㅠ..

https://sw-ko.tistory.com/87