https://www.acmicpc.net/problem/9466
문제
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.
1 | 2 | 3 | 4 | 5 | 6 | 7 |
3 | 1 | 3 | 7 | 3 | 4 | 6 |
위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.
주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
문제 풀이
사이클이 있는지 판별하는 dfs 문제.
본인이 선택한 사람을 따라 dfs하면 언젠가 이미 방문한 사람을 다시 방문하게 된다. 재방문하기 전까지의 dfs 스택에서 하나씩 pop하면서 스택에 재방문한 사람의 번호가 있는지 확인한다. 만약 있다면 사이클이 형성된 것이고, 재방문한 사람과 pop한 번호의 사람들끼리는 팀을 이룰 수 있다. 스택이 빌 때까지 재방문한 사람의 번호가 없다면 사이클이 형성되지 않았으므로 팀을 이룰 수 없다.
아래는 코드.
#include <iostream>
#include <stack>
using namespace std;
stack<int> dfsStack;
bool* isVisited;
int* arr;
int canMakeTeamStudent = 0;
int getPoppedCount(int i)
{
int count = 0;
while (!dfsStack.empty())
{
count++;
if (dfsStack.top() == i)
{
return count;
}
dfsStack.pop();
}
return 0;
}
void dfs(int i)
{
isVisited[i] = true;
dfsStack.push(i);
while (!dfsStack.empty())
{
int top = dfsStack.top();
int next = arr[top];
if (isVisited[next] == true && next==i)
{
canMakeTeamStudent += dfsStack.size();
break;
}
else if (isVisited[next] == true)
{
int poppedCount = getPoppedCount(next);
canMakeTeamStudent += poppedCount;
break;
}
else
{
dfsStack.push(next);
isVisited[next] = true;
}
}
}
void reset()
{
while (!dfsStack.empty())
{
dfsStack.pop();
}
}
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 0; t < T; t++)
{
int N;
cin >> N;
arr = new int[N + 1];
isVisited = new bool[N + 1];
canMakeTeamStudent = 0;
for (int i = 1; i < N + 1; i++)
{
cin >> arr[i];
isVisited[i] = false;
}
for (int i = 1; i < N + 1; i++)
{
if (isVisited[i] == false)
{
dfs(i);
reset();
}
}
cout << N - canMakeTeamStudent << "\n";
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준 30460] 스위치 (C++) (0) | 2024.04.06 |
---|---|
[백준 14002] 가장 긴 증가하는 부분 수열 4 (C++) (0) | 2024.04.05 |
[백준 2003] 수들의 합 2 (C++) (0) | 2024.04.03 |
[백준 17179] 케이크 자르기 (C++) (0) | 2024.04.02 |
[백준 25194] 결전의 금요일 (C++) (0) | 2024.03.31 |