[BOJ] C++ 9466 텀 프로젝트 - BFS 심화

9466번: 텀 프로젝트

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

ans :
3
0

---

처음에는 평범한 BFS를 사용한 O(n^2) 풀이를 떠올렸다. BFS를 이용해 자기 자신을 다시 만나면 사이클 안이라서 팀, 자기 자신이 아닌 방문한 곳을 만난다면 사이클 밖이라서 팀이 아닌 것으로 판단하였다. 그러나 시간초과에 걸려서 다른 풀이를 떠올려야 했다. 아래의 풀이는 O(n^2) 풀이이다.

/** BFS 9466 텀 프로젝트 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

bool bfs(int n, int start, int arr[])
{
    queue<int> Q;
    int visited[n + 1] = {
        0,
    };
    Q.push(start);

    while (!Q.empty())
    {
        int cur = Q.front();
        Q.pop();

        int next = arr[cur];
        if (next == start)
            return true;
        if (visited[next] == 1)
            return false;
        visited[cur] = 1;
        Q.push(next);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int stu[n + 1];
        for (int i = 1; i < n + 1; i++)
            cin >> stu[i];
        int res = 0;
        for (int i = 1; i < n + 1; i++)
            if (!bfs(n, i, stu))
                res++;

        cout << res << '\n';
    }
}

---

O(n)으로 풀려면 테이블을 n번 순회하면서 사이클을 판단해야 한다. 기존의 O(n^2) 풀이에서 최적화를 하면 O(n)으로 풀 수 있을 것 같았다.

 

1. 이미 이룬 팀은 순회에서 제외해도 된다.

2. 1 -> 3 / 2 -> 1 -> 3 이런 식의 방문은 1 -> 3이 중복되므로 제외할 수 있다.

 

이 두 점을 최적화 하면서도 bfs를 생각해 보면 x번부터 방문을 시작하다가 사이클이 나오면 사이클만 방문 표시를 지우고 사이클로 표시하고, 이런 방식을 떠올렸다. 예를 들면 아래와 같은 상황이다.

이 알고리즘을 메인으로 나머지 최적화도 할 수 있었다.

 

/** BFS 9466 텀 프로젝트 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int stu[100005];
int visited[100005]; //-1은 사이클 안, 0은 방문한 적 없음.
int n;

void bfs(int start)
{
    int cur = start;
    while (1)
    {
        // cur 방문
        visited[cur] = start;
        // cur 다음 단계로
        cur = stu[cur];
        if (visited[cur] == start)
        {
            // 이번 start에서 시작된 방문에서 방문된 곳을 들리면 사이클을 찾은 것
            while (visited[cur] != -1)
            {
                visited[cur] = -1;
                cur = stu[cur];
            }
            return;
        }
        // 이번 방문이 아닌 지난 방문에서 방문된 곳을 들리면 지금까지 들린곳 전부 사이클이 아니다.
        else if (visited[cur] != 0)
            return;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i < n + 1; i++)
        {
            cin >> stu[i];
            visited[i] = 0;
        }

        for (int i = 1; i < n + 1; i++)
        {
            if (visited[i] == 0)
                bfs(i);
        }

        int res = 0;

        for (int i = 1; i < n + 1; i++)
        {
            if (visited[i] != -1)
                res++;
        }

        cout << res << '\n';
    }
}