문제 출처

1. 문제설명

  • 그래프가 주어진다.
  • 그래프는 자기 자신 혹은 다른 노드를 가리키고 있다.

  • 이 때 사이클이 형성되면 팀이 되고, 사이클이 형성되지 않으면 팀이 될 수 없다.

  • 예제
    • 3은 자기 자신을 가리키고 있다.
      • 즉, 사이클이 있다.
    • 4->7->6->4 순으로 가리키고 있다.
      • 즉, 사이클이 있다.
    • 그 외에 사이클은 존재하지 않는다.
    • 따라서, 팀에 속하지 않은 1, 2, 5 즉 3이 정답이 된다.



2. 알고리즘 설계

  • 이 문제의 핵심은 구현이 아니다.
  • 한번 들른 곳은 다시 안 들려야 하는 게 관건이다.
  • 처음에 DFS로 구현했을 때, 시간 초과를 당했다.



3. 로직

  • 방문했음을 알리는 visit 배열을 사용
    • 이는 각 노드를 돌 때마다 갱신시켜줘야 한다.
  • move 배열
    • 이미 들른 적이 있는 노드인가?



4. 전체 코드

#include<iostream>
using namespace std;

const int sz = 100002;

int arr[sz], _move[sz], visit[sz];

int search(int start)
{
	int idx = start;
	int cnt = 1;

	while (true) {
		if (_move[idx]) {  // 방문한 적이 있다면,
			if (start != visit[idx])  // 시작과 같지 않으면, 사이클이 없는 것
				return 0;

			return cnt - _move[idx];  // 사이클의 수를 계산하여 리턴
		}
        // 방문하지 않은 노드라면, 갱신
		_move[idx] = cnt++;
		visit[idx] = start;
		idx = arr[idx];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int tc; cin >> tc;
	while (tc--) {
		int n, result = 0;
		cin >> n;

		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			_move[i] = 0;
			visit[i] = 0;
		}

		for (int i = 1; i <= n; i++)
			if (!_move[i])
				result += search(i);

		cout << n - result << '\n';
	}
	return 0;
}

5. 소감

  • 시간 초과 때문에 진짜 엄청 고민했던 문제
  • 처음 구현에는 move 배열 없이 구현하려고 했는데,
  • 이게 시간을 잡아먹은 주요 원인이었다…