[백준 24526] 전화 돌리기

문제 링크 : 24526번: 전화 돌리기 (acmicpc.net)

24526번: 전화 돌리기

---

 

사이클을 어떻게 처리해야 할지 고민을 했던 문제이다.

우선 방문배열을 2차원 배열 형태(visited[100001][2])로 선언하여 다음과 같이 처리하도록 하였다.

 

• visited[x][0] : 노드 x가 최초로 방문되었는지 판단하기 위한 용도이며 true로 마킹된 경우 방문한 경우다.
• visited[x][1] : DFS를 통해 노드 x에 방문되면 true로 마킹하고 DFS가 끝나게 될 경우 false로 마킹한다.

그리고 사이클인지 아닌지를 판단하기 위해 배열(cycle[100001])을 선언하였다.

2가지 케이스만 보도록 하자.

 

① cycle 인 경우

 

 

DFS(1) 을 호출하여 1번 노드부터 시작하여 그래프 탐색을 시도한다고 해보자.

 

1. 1번 노드를 방문하였으므로 visited[1][0] = visited[1][1] = true 로 지정하고 DFS(2) 호출
2. 2번 노드를 방문하였으므로 visited[2][0] = visited[2][1] = true 로 지정하고 DFS(3) 호출
3. 3번 노드를 방문하였으므로 vsiited[3][0] = visited[3][1] = true 로 지정하고 DFS(1) 호출

1번 노드를 다시 방문하였으므로 사이클이라고 판단하기엔 약간 어려움이 있다.

따라서 visited[1][0] 값을 통해 해당 노드의 방문 여부를 판단하고,

visited[1][1] 값을 통해 사이클 여부를 판단하면 된다.

 

정리하자면 다음과 같다.

 

• visited[x][0] = true 인 경우
  • visited[x][1] = true : cycle 이 형성됨
  • visited[x][1] = false : cycle 이 형성되지 않음

으로 판단이 가능하다.

 

 

② cycle 이 아닌 경우

 

cycle 이 아닌 경우지만 특정 그래프의 cycle 을 판단하는데 있어서 약간의 멘붕이 있었다.

단 하나의 visited 배열로 처리하기에는 사이클 판단이 어렵다는 것이다.

다음 케이스를 보면 바로 이해가 가능하다.

 

 

3번 노드의 진입차수가 1을 넘을 때 사이클을 판단하는데 약간의 어려움이 존재했다.

동일하게 DFS(1) 을 호출하여 1번 노드부터 시작하여 그래프 탐색을 시도한다고 해보자.

 

1. 1번 노드를 방문하였으므로 visited[1][0] = visited[1][1] = true 로 지정하고 DFS(2) 호출
2. 2번 노드를 방문하였으므로 visited[2][0] = visited[2][1] = true 로 지정하고 DFS(3) 호출
3. 3번 노드를 방문하였으므로 visited[3][0] = visited[3][1] = true 로 지정한다.
4. 3번 노드가 다음 노드로 방문할 노드가 없으므로 visited[3][1] = false 로 지정하고 DFS 리턴
5. 2번 노드가 다음 노드로 방문할 노드가 없으므로 visited[2][1] = false 로 지정하고 DFS 리턴 

위와 같이 방문 처리를 해준 후 1번 노드에서 DFS(3) 을 호출한다.

이 때, visited[3][0] 값은 true 이므로 이를 cycle 이라고 할 수 있을까?

따라서, 고민을 통해 DFS 가 끝난 노드는 방문이 끝났다는 것을 확인하기 위한 추가 방문 배열이 필요했던 것이다.

추가 방문 배열이 결국 visited[3][1] 이며 false 로 마킹되었기 때문에 이 그래프는 cycle 이 아니다.

 

따라서 cycle 이 발생하는 그래프와 발생하지 않은 그래프를 각 노드마다 마킹한 후에,

1번 노드부터 N번 노드까지 cycle 이 발생하지 않는 경우를 카운팅하여 카운팅한 결과를 출력하면 된다.

시간 복잡도는 O(N) 으로 해결 가능하다.

 

풀이 코드

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
vector<int> v[100001];
bool visited[100001][2], cycle[100001];

void input() {
	int U, V;

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> U >> V;
		v[U].push_back(V);
	}
}

bool dfs(int x) {
	if (v[x].size() == 0) {
		visited[x][0] = true;
		visited[x][1] = false;
		return false;
	}
	if (visited[x][0]) {
		if (visited[x][1] || cycle[x]) 
			return true;
		else 
			return false;
	}
	visited[x][0] = visited[x][1] = true;
	for (int next : v[x]) {
		cycle[x] |= dfs(next);
	}
	visited[x][1] = false;
	return cycle[x];
}

void solution() {
	int ans = 0;

	for (int i = 1; i <= N; i++) {
		if (visited[i][0]) continue;
		dfs(i);
	}
	for (int i = 1; i <= N; i++) {
		if (!cycle[i]) ans++;
	}
	cout << ans;
}

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

	input();
	solution();

	return 0;
}