9466 텀 프로젝트 C++ 문제 설명 및 풀이

안녕하세요 판타지코딩월드입니다!

 

오늘은 9466번 텀 프로젝트 문제 C++로 설명 및 풀이 하겠습니다.

---

1. 문제 설명

 

이 문제는 각 학생이 함께 프로젝트를 진행하길 원하는 학생 번호를 제시하면, 원하는 학생끼리 팀을 꾸려 몇 명의 학생이 팀 꾸리기에 성공했는지를 알아보는 문제이다. 답으로는 프로젝트 팀에 합류하지 못한 학생 수를 출력한다. 아래 예시 사진으로 어떤 의미인지 이해해 보자.

예시 그림

 

1, 2, 3, 4, 5 학생이 각각 2, 3, 3, 5, 4 번 학생과 함께 프로젝트 팀을 꾸리길 원한다. 프로젝트 팀 꾸리기가 가능한 경우는 1->2, 2->3, 3->1 이런 형태로 서로가 원하거나, 3->3 처럼 자기 혼자 하길 원하는 경우이다. 위의 예시에서 몇 개의 팀이 꾸려지는지 확인해보자. 먼저 1번 학생은 2번 학생을 원한다. 그리고 2번 학생은 3번 학생을 원한다. 그러나 3번 학생이 3번을 원하므로 혼자서 프로젝트를 하길 원한다. 그래서 3->3 만 프로젝트 팀 꾸리기에 성공했다. 다음으로 4번 학생은 5번 학생을 원하고, 5번 학생이 4번 학생을 원하므로 팀 생성 조건에 부합한다. 그러므로 여기서는 3, 4, 5번 학생이 팀 꾸리기에 성공했고, 1, 2번 학생이 실패했다. 그러므로 2를 출력하면 정답이 된다.

 

 

2. 문제 풀이

 

이 문제를 풀기 위해서는 dfs를 활용한다. 각 학생의 번호로 들어가서 어느 학생을 원하는지 확인하고, 다음 학생으로 dfs를 수행해서 다시 첫 학생으로 돌아올 수 있는지를 확인한다.

 

• dfs 활용

int s[100001];  // 각 학생이 원하는 학생을 저장할 배열
bool done[100001];  // 매칭을 완료한 학생
bool check[100001];  // 방문한 학생
int cnt = 0;  // 매칭 완료 학생 수

void dfs(int start)
{
    check[start] = true;  // 방문 처리
    int next = s[start];  // start번 학생이 원하는 학생 번호 저장
    if(!check[next])  // 방문한 적 없는 학생 여부 확인
    {
        dfs(next);  // 다음 학생 탐색
    }
    else if(!done[next])  // 이미 방문했지만 팀 매칭이 되지 않았다면 매칭 처리
    {
        for(int i=next; i!=start; i=s[i])  // 팀 생성 조건 만족하는 학생 목록 반복하여 학생 수 세기
        {
            cnt++;  // start 학생 제외하고 몇 명인지 세기
        }
        cnt++;  // start 학생도 세어 주기
    }
    done[start] = true;  // 방문한 학생은 매칭 완료 처리
}

 

dfs를 활용해서 프로젝트 생성 조건을 만족하는지 확인하기 위한 코드이다. 연결 된 학생을 확인하여 다시 시작 학생 번호로 돌아올 수 있는지 확인한다. check 함수에 방문 한 학생은 true 처리를 하여 true 처리 된 학생 번호에 다시 돌아온다면 매칭 완료 여부를 확인하고 연결 된 학생의 수를 세어준다. 이 때 start 학생의 경우는 for문으로 세어주지 않기 때문에 for문 종료 후 해당 학생 수까지 세어 주기 위해 cnt++를 한 번 더 해준다. 

 

마지막으로 done 배열에서 start 학생에 true 처리를 하는데, 이 경우는 시간 초과를 방지하기 위함이다. dfs의 특성상 한 번 방문한 학생에서 연결 된 다른 학생의 모든 경우의 수를 탐색하게 된다. 그러므로 한 번 방문 했을 때 매칭되지 않는다면 다시 방문했을 때 또한 같은 결과일 것이기 때문에 재방문을 하지 않도록 start 학생에 대해 true 처리를 한다.

 

• for문

for(int j=1; j<=n; j++)
{
    if(!check[j])
    {
        dfs(j);
    }
}

 

방문하지 않은 학생일 경우 dfs를 실행해서 프로젝트 팀 매칭을 수행한다.

 

 

3. 전체 코드

 

#include <iostream>
#include <string.h>

using namespace std;

int s[100001];
bool done[100001];
bool check[100001];
int cnt = 0;
void dfs(int start)
{
    check[start] = true;
    int next = s[start];
    if(!check[next])
    {
        dfs(next);
    }
    else if(!done[next])
    {
        for(int i=next; i!=start; i=s[i])
        {
            cnt++;
        }
        cnt++;
    }
    done[start] = true;
}

int main()
{
    int T;
    cin >> T;
    for(int i=0; i<T; i++)
    {
        cnt = 0;
        int n;
        cin >> n;
        for(int j=1; j<=n; j++)
        {
            cin >> s[j];
        }
        
        for(int j=1; j<=n; j++)
        {
            if(!check[j])
            {
                dfs(j);
            }
        }
        cout << n-cnt << endl;
        memset(check, 0, sizeof(check));
        memset(s, 0, sizeof(s));
        memset(done, 0, sizeof(done));
    }
}

 

테스트 케이스가 있는 문제이기 때문에 각 케이스 종료 시 배열 초기화를 하여 불필요한 데이터가 저장되어서 오류를 발생시키지 않도록 해야 한다. 그리고 dfs 활용 방법을 이해하면 문제 풀이에 도움이 될 것이다.

---

오늘은 C++을 활용한 문제 설명과 풀이 방법을 알아보았습니다.

 

감사합니다!