백준 9466번
오늘 풀어본 문제는 백준의 9466번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이 $(s_1, s_2, …, s_r)$ 이라 할 때, $r=1$ 이고 $s_1$ 이 $s_1$ 을 선택하는 경우나, $s_1$ 이 $s_2$ 를 선택하고, $s_2$ 가 $s_3$ 를 선택하고,…, $s_{r-1}$ 이 $s_r$ 을 선택하고, $s_r$ 이 $s_1$ 을 선택하는 경우에만 한 팀이 될 수 있다.
예를 들어, 한 반에 $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 \le n \le 100,000)$ 으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 $1$ 부터 $n$ 까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
풀이과정
1번째 시도
문제를 해결하기 위해 떠올린 방법은 각 학생의 번호를 정점으로 하고 각각의 선택을 방향이 있는 간선으로 하는 그래프를 구성한 뒤, DFS를 이용하여 어떤 정점에서 출발하여 자기 자신으로 돌아올 수 있는지를 검증하는 것이었다.
또한 시간이 너무 오래 걸릴 것을 염두에 두고, 탐색 과정에서 어떤 정점에서 자기 자신으로 되돌아 올 수 있는 것이 확인되면 해당 루프의 모든 정점도 각각 자기자신으로 되돌아 올 수 있기 때문에, 이를 저장해두도록 하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
void simulate();
void search(int start, const vector<int>& graph, vector<int>& result);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int i=0; i<T; i++) {
simulate();
}
return 0;
}
void simulate() {
int n, alone = 0;
cin >> n;
vector<int> graph(n+1, 0);
vector<int> result(n+1, 0);
for (int i=1; i<=n; i++) {
cin >> graph[i];
}
for (int i=1; i<=n; i++) {
if (result[i] == 0) {
search(i, graph, result);
}
}
for (int i=1; i<=n; i++) {
if (result[i] == -1) {
alone++;
}
}
cout << alone << "\n";
}
void search(int start, const vector<int>& graph, vector<int>& result) {
int n = result.size() - 1;
vector<bool> visited(n + 1, false);
int curr = start;
while (!visited[curr] && result[curr] == 0) {
visited[curr] = true;
curr = graph[curr];
}
if (curr == start) {
for (int i=1; i<=n; i++) {
if (visited[i]) {
result[i] = 1;
}
}
}
else {
result[start] = -1;
}
}
실행 결과 ‘시간 초과’ 가 떴다.
2번째 시도
시간 초과의 원인으로 알아낸 것은, 루프를 형성하지 못하는 정점들이 여러 번 확인되는 것이었다. 자기 자신으로 되돌아올 수 없는 정점들도 바로 저장하도록하여 시간 초과 해결을 시도하였다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
void simulate();
void search(int start, const vector<int>& graph, vector<int>& result);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
for (int i=0; i<T; i++) {
simulate();
}
return 0;
}
void simulate() {
int n, alone = 0;
cin >> n;
vector<int> graph(n+1, 0);
vector<int> result(n+1, 0);
for (int i=1; i<=n; i++) {
cin >> graph[i];
}
for (int i=1; i<=n; i++) {
if (result[i] == 0) {
search(i, graph, result);
}
}
for (int i=1; i<=n; i++) {
if (result[i] == -1) {
alone++;
}
}
cout << alone << "\n";
}
void search(int start, const vector<int>& graph, vector<int>& result) {
int n = result.size() - 1;
vector<bool> visited(n + 1, false);
int curr = start;
while (!visited[curr] && result[curr] == 0) {
visited[curr] = true;
curr = graph[curr];
}
if (curr == start) {
result[start] = 1;
for (curr = graph[start]; curr != start; curr = graph[curr]) {
result[curr] = 1;
}
}
else {
result[start] = -1;
for (int fail = graph[start]; fail != curr; fail = graph[fail]) {
result[fail] = -1;
}
if (result[curr] == 0) {
start = curr;
result[start] = 1;
for (curr = graph[start]; curr != start; curr = graph[curr]) {
result[curr] = 1;
}
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
길고 긴 여정 끝에, 드디어 CLASS 5 를 달성하였다!!!
그러나 본 게임은 지금부터가 될 것이다. 이제 CLASS 5의 모든 에센셜 문제를 푼 뒤, 최종적으로 군입대 전까지 CLASS 5 MASTER 에 도달할 수 있도록 최선을 다해야 할 것이다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/9466