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

문제

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

9466번: 텀 프로젝트

 

풀이 과정

 

싸이클이 형성되면 팀이 생성된다.

---

싸이클이 형성되는 경우

 

1) 첫번째 노드와 마지막 노드가 같을 경우

 

4 - 7 - 6 - 4

 

2) n번째 노드와 미지막 노드가 같을 경우

 

2 - 1 - 3 - 3

 

 

🚩 반드시 알아야 할 것

• 재방문으로 사이클 형성을 알 수 있다.
• 재방문 노드 이전의 노드들 (경로)은 사이클 형성 불가한 노드라는게 판정된다.
  • 첫번째 노드를 1, 2, 3 .. 로 진행하다가 5 - 6 - 1 - 2- 1 를 진행하게 됐다.
  • 6 - 1 - 2 - 1 를 탐색했으니까.
  • 5, 6은 사이클 형성 불가다.
  • 6을 첫번째 노드로 탐색하지 않아도 된다.
    
    이렇게  각 노드를 한번씩 방문하여 시간 초과가 나지 않도록 신경 써야 한다. O(n)

 

소스 

 

경로를 저장하기 위해 queue를 사용했다.

• teamed은 팀 형성 여부 저정용
• visited는 재방문으로 싸이클 판단용

 

？ 탐색을 하다가 중간에 이미 탐색하면서 사이클 못만든다고 나온 노드가 나온다면?
queue에 저장하고 있던 경로들도 사이클을 못 만든다고 표시 해준다.

 

？ 탐색하다가 이미 팀을 만든 친구들이 나온다면?

지금 노드도 포함해서 만들 수 있는지 모르겠으니까 걍 경로를 싹 지워준다..

 

？ 팀 형성 판단도 안된 노드인데 재방문이다?

재방문 노드부터 싸이클 형성 가능하다!

재방문 노드 이전은 사이클 형성 불가능이라고 표시해주고 큐에서 날려버린다. 

main문에서 queue에 남은 노드들만 사이클 가능 표시를 해준다. 

 

#include <iostream>
#include <queue>
#include <memory.h>
#define MAX 100001

bool visited[MAX+1];
int teamed[MAX+1];
int pick[MAX+1];
int N = 0;
std::queue<int> q;

void DFS(int i)
{
    int temp = 0;
    if(teamed[i] == -1)
    {
        while(!q.empty())
        {
            temp = q.front();
            teamed[temp] = -1; // team 구성 불가.
            q.pop();
        }
        return;
    }
    
    if(teamed[i] == 1)
    {
        while(!q.empty())
        {
            q.pop();
        }
        return;
    }
    
    if(visited[i])
    {
        while(!q.empty())
        {
            temp = q.front();
            if(temp == i)
                break;
            teamed[temp] = -1; // team 구성 불가.
            q.pop();
        }
        return;
    }
    
    q.push(i);
    visited[i] = true;
    DFS(pick[i]);
}

int main()
{
    int T=0; std::cin >> T;

    while(T--)
    {
        int result = 0;
        int temp = 0;
        std::cin >> N;
        memset(pick, 0, sizeof(pick));
        memset(teamed, 0, sizeof(teamed));
        memset(visited, false, sizeof(visited));

        //input
        for(int i=1; i<=N; ++i)
        {
            std::cin >> pick[i];
        }
        
        //solve
        for(int i=1; i<=N; ++i)
        {
            DFS(i);
            while(!q.empty())
            {
                temp = q.front(); q.pop();
                teamed[temp] = 1;
            }
        }
        
        //output
        for(int i=1; i<=N; ++i)
        {
            if(teamed[i]!=1)
                ++result;
        }
        std::cout << result <<'\n';
        
    }//T
    return 0;
}