[2020 카카오 인턴십] 동굴 탐험

programmers.co.kr/learn/courses/30/lessons/67260

코딩테스트 연습 - 동굴 탐험

tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

#include <vector>
#include <queue>

using namespace std;

bool dfs(vector<vector<int>> &adj, vector<int> &visited, int curr) {
	// curr에서 출발하는 경로에 사이클이 존재하는지를 확인
	if (visited[curr] == 1) return false;
	if (visited[curr] == 2) return true;

	visited[curr] = 1;

	for (int next : adj[curr]) {
		if (!dfs(adj, visited, next)) return false;
	}
	visited[curr] = 2;
	return true;
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
	// undirected 그래프 adj1 만들기
	vector<vector<int>> adj1(n);

	for (vector<int> p : path) {
		adj1[p[0]].push_back(p[1]);
		adj1[p[1]].push_back(p[0]);
	}

	// directed 그래프 adj2 만들기
	vector<vector<int>> adj2(n);
	vector<bool> visited1(n, 0);
	queue<int> q1;

	q1.push(0);

	while (!q1.empty()) {
		int curr = q1.front();
		q1.pop();
		visited1[curr] = true;

		for (int next : adj1[curr]) {
			if (!visited1[next]) {
				adj2[next].push_back(curr);
				q1.push(next);
			}
		}
	}

	for (vector<int> o : order) {
		adj2[o[1]].push_back(o[0]);
	}

	// dfs
	vector<int> visited2(n, 0);
	for (int i = 0; i < n; i++) {
		if (!dfs(adj2, visited2, i)) return false;
	}
	return true;
}

 

문제를 읽고 느낌상 데드락 감지처럼 사이클을 찾는 문제일 것이다 싶었는데

그 이상 진도를 나가지 못하여.. 결국 풀이를 참고했다 (카카오에서 올린 풀이가 잘 되어있음)

 

일단 path 배열을 읽어서 undirected 그래프(adj1)를 만든다.

카카오 풀이를 보면 나중에 방문하는 노드가 먼저 방문해야 하는 노드를 가리키도록 그래프를 만들라고 되어 있으므로 위에서 만든 adj1을 다시 탐색해서 directed 그래프(adj2)를 만든다.

그리고 order를 읽어서 문제에서 주어진 방문 순서를 그래프에 추가한다.

 

이렇게 만들어진 그래프에 사이클이 존재하면 false를 반환해야 한다.

 

나는 DFS로 풀었다.

dfs() 함수의 역할은 'curr에서 출발하는 경로에 사이클이 존재하는지 확인하는 것'이다.

 

키포인트는 방문여부를 저장하는 visited2 배열인데

아직 방문하지 않은 노드는 0으로,

방문중인 노드는 1로,

방문을 마친 노드는 2으로 표시한다.

 

만약 현재 방문해야 하는 노드의 visited2 값이 1이면 사이클이 발견된 것이므로 false를 반환한다.

그리고 visited2 값이 2면 방문을 마친 노드이기 때문에

이미 사이클이 존재하지 않는다는 것을 확인한 것이므로 그대로 true를 반환해준다.

(이렇게 하면 이미 탐색을 마친 노드에 대해서는 더 이상 탐색을 하지 않으므로 시간복잡도를 줄일 수 있다.)