백준 9466 - 텀 프로젝트

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

간단해보여서 접근했는데.. 분기 조건을 찾는 데도 좀 헤맸고 구현에도 애를 좀 먹었다. 낮은 난이도 문제부터 다시 풀면서 깔끔한 구현을 연습해야겠음

0.

모든 정점의 사이클 포함 여부를 파악해야 하는 문제이다. 단순하게 모든 정점에서 출발하는 DFS로는 시간 초과를 해결할 수 없다. 시간 단축의 핵심은, 매 DFS마다 한 번의 DFS를 통해 도달할 수 있는 모든 정점의 사이클 포함 여부를 파악해 저장하는 것이다. 사이클에 포함되든 안되든 포함 여부가 결정되기만 하면 된다. 그게 가능한 이유는 다음 장을 보자.

1.

각 정점에서 DFS를 출발했을 때 마주하게 되는 경우를 모두 따져보자.

 

- 시작 정점의 간선이 자기 자신을 가리킬 경우

- 시작 정점에서부터 간선을 따라 쭉 이동해 시작 정점에 도달하는 경우

개꿀이다. 위 연결 그래프의 어디서 출발해도 자신이 싸이클에 속한다는 걸 확인할 수 있다.

 

- 탐색하는 도중에 이미 존재하는 사이클을 발견할 경우

 

 

불쌍한 5는 사이클에 포함되지 않는다.

그런데 여기서, 5가 2 - 3 - 4를 훑지 않아도 이 사실을 깨달을 수 있다면, 5는 조금이라도 덜 비참해지지 않을까?

 

2.

이번 DFS에서는 기본 DFS를 위한 visited 배열 외에 cycle 배열을 사용한다. cycle 배열의 원소는 사이클에 포함됨/포함되지 않음/ 아직 포함여부를 모름 의 3가지 상태를 가질 수 있다. 그 값을 순서대로 1, -1, 0이라고 하자.

 

위 그림을 다시 보자.

2, 3, 4는 이미 자기들끼리 사이클을 형성했다. 여기서 5가 손을 뻗어봤자 5를 포함한 사이클이 형성될 수 있을까? 불가능하다. 이들의 손은 하나뿐이고, 5에게 건넬 손은 더이상 남지 않았다.

 

그럼 이 경우는 어떨까?

- 탐색하는 도중에 사이클에 포함되지 않는 정점을 발견할 경우

 

다음 그림을 보자.

아무것도 모르는 6은 이미 팽 당한 5에게 다가간다. 하지만 이미 2-3-4 서클에 마음을 빼앗긴 5가 6의 제안을 받아들일 리 만무하다. 6에게 돌아올 답신 따위는 없다.

 

이 슬픈 이야기의 교훈은, 현재 노드 i가 가리키는 정점 j의 사이클 포함 여부가 정해져있기만 하면, i는 반드시 사이클에 포함되지 않는다는 것이다.

3.

이런 문제도 있다. 개인적으로 이번 이야기가 제일 슬프다.

 

- 탐색 중 경로 내부에서 새로운 사이클을 발견하는 경우

안도의 한숨을 내쉬던 1은 5의 배신으로 인해 사이클에서 낙오되었다. 눈물이 앞을 가린다....

 

어쨌든 우리는 할 일을 해야한다. DFS 경로 상의 모든 정점이 사이클 여부가 결정되지 않았다. 하지만 마지막 정점은 시작 정점을 가리키지 않는다. 이 경우 우리는 내부에 사이클이 생겼다고 판단할 수밖에 없다. 따라서 경로를 역추적하며 마지막 정점이 가리키는 정점을 찾고, 이 구간은 cycle 값을 1로, 나머지 구간은 전부 -1로 갱신한다.

 

이제 앞전의 내용을 종합하면, 매 DFS마다 우리는 3가지 결과 중 하나를 만날 수 있으며, 그때마다 다음과 같은 액션을 취하면 된다.

---

1) DFS 도중에 중단되는 경우

→ 사이클 확인한 정점 j를 만났다는 뜻이므로 j 앞까지 모든 정점에 사이클이 없다고 표시한다.

 

2) DFS가 중단되지 않았는데, DFS 마지막 정점이 시작 정점을 가리키는 경우

→ 경로 전체가 사이클이므로 모든 정점에 사이클이 있다고 표시한다.

 

3) DFS가 중단되지 않았는데, DFS 마지막 정점이 시작 정점을 가리키지 않는 경우

→ 내부에 사이클이 존재하므로, 경로를 역추적하며 사이클을 찾아 1을 표시하고 나머지 정점은 -1을 표시한다

---

 

말이 참 길었는데... 결론적으로 말하면 매 DFS마다 3가지 분기에 따라 path를 이용해 사이클 포함 여부를 표시해주면 된다. 참고로 cycle 배열은 DFS가 끝날 때까지 갱신되지 않으므로 DFS를 위해서는 별도의 방문 처리를 해줘야 한다.

 

소스 코드

//0 : 모름, 1 : 있음, -1 : 없음
int cycle[100001];

void solve() {
	//매 TC마다 초기화
	memset(cycle, 0, sizeof(cycle));
	
    //입력
	int N; cin >> N;
	vector<int> arr(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	for (int i = 1; i <= N; i++) {
		stack<int> path;
        
        //매번 visited 초기화하는 것보다 빠름
		set<int> visited;

		//이미 확인했을 수도 있음
		if (cycle[i]) continue;
		
		int nxt = i;
		bool flag = 0;
		
		//DFS
		while (visited.find(nxt) == visited.end()) {
			if (cycle[nxt]) {
				flag = 1;
				break;
			}
			visited.insert(nxt);
			path.push(nxt);
			nxt = arr[nxt];
		}

		//도중에 중단
		if (flag) {
			while (!path.empty()) {
				cycle[path.top()] = -1;
				path.pop();
			}
		}

		//경로 전체가 사이클
		else if (nxt == i) {
			while (!path.empty()) {
				cycle[path.top()] = 1;
				path.pop();
			}
		}

		//경로 내부에 사이클
		else {
			while (!path.empty()) {
				int top = path.top();
				cycle[top] = 1;
				path.pop();

				if (top == nxt)
					break;
			}

			while (!path.empty()) {
				cycle[path.top()] = -1;
				path.pop();
			}
				
		}
		
	}

	cout << count(cycle + 1, cycle + N + 1, -1) << endl;
}