어제부터 IUPC를 대비해서 역대 IUPC 문제들을 풀어보고 있다. 어제는 1회를 풀었는데 컨디션이 안 좋았는지 실력이 안 좋았는지 둘 다 안좋았는지 여튼 생각만큼 많이 못풀었다. 이것저것 많이 틀리기도 하고 생각을 못했던 것도 있고, 여전히 못하는 것들도 있다. 어짜피 우승이 목적이 아니기 때문에 ^^ 오답의 순서는 내 맘대로다 ㅎ
1. 문제 설명
Description을 요약하면 1 → N까지의 길에 Cycle이 있는 지를 찾는 문제였다. 내가 선택한 경로가 Cycle이 없더라도, 일단 갈 수 있는 길에 Cycle이 있으면 Cycle이 있다고 판단해야 한다.
민지를 도와 어떠한 길을 선택하더라도 같은 교차로를 다시 방문하는 경우가 있는지 없는지를 판단하는 프로그램을 작성하자.
라고 써있다. 그리고 1부터 N이다. 처음에 이걸 잘못 읽어서 헛짓을 좀 했었다.. 문제 잘 읽자....
2. 아이디어
Cycle을 찾는 방법은 여러가지가 있지만 개인적으로는 DFS를 돌리면서 visit 배열을 int형으로 선언하고 3가지의 상태로 관리하는 것을 선호하는 편이다. 이 방법에 대해 조금 더 설명하자면,
0 - Unvisit
1 - Visit(But, not done yet)
2 - Visit(Done)
의 3가지 상태를 갖는다. 0인 상태는 한 번도 방문하지 않은 상태이다. 1인 상태는 방문했지만 자신이 호출한 재귀가 끝나지 않은 상태이다. 2는 자신이 호출한 재귀가 모두 처리되고 자신도 마지막으로 닫아준 상태이다.
이런 상태를 가지고 있다면, 만약 어떤 정점을 방문했을 때, 이미 visit의 값이 1이라면, 해당 정점을 호출한 정점을 쭉 거슬러 올라가다보면 자신이 방문하려고 했던 정점이 있을 것이다! 이 의미는? Cycle이 존재한다는 의미이다!
이러한 경우에는 Cycle이 있는 상태이므로 "CYCLE"을 출력하고 끝내주면 된다. N까지 모두 방문하였는데도 Cycle이 없다면 "NO CYCLE"을 출력해주면 된다.
3. 소스 코드
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[101];
int visit[101];
void dfs(int here) {
if (visit[here] == 1) {
cout << "CYCLE\n";
exit(0);
}
visit[here] = 1;
for (auto i : graph[here]) {
if (visit[i] != 2) dfs(i);
}
visit[here] = 2;
}
int main()
{
int N, M, C;
cin >> N;
for (int i = 1; i < N; i++) {
cin >> M;
while (M--) {
cin >> C;
graph[i].push_back(C);
}
}
dfs(1);
cout << "NO CYCLE\n";
}뭔가 별 거 아닌데 오늘은 vector를 돌면서 auto를 써보고 싶었다. 항상 알기만 하고 쓰지는 않았는데 뭔가 편하다! exit(0);은 사실 좋은 습관인지 안 좋은 습관인지는 잘 모르겠지만 flag 처리를 해주지 않아도 쌓여있는 재귀를 탈출할 수 있다는 점이 편해서 가끔 DFS 할 때만 쓴다..(자매품 goto)