백준 16964번 : DFS 스페셜 저지 - DFS, C++

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

16964번: DFS 스페셜 저지

 

1. 문제설명

입력으로 N개의 노드가 주어지고 노드간의 연결관계가 주어진다.

그리고 마지막 입력으로 DFS 방문 순서가 주어진다.

노드간의 연결관계를 바탕으로 깊이우선탐색을 할 때

주어진 방문 순서처럼 방문할 수 있는지 여부를 묻는 문제이다.

 

2.접근방법[알고리즘]

접근 방법은 문제 이름부터 DFS이기 때문에 쉽게 알 수 있다.

하지만 이 문제를 푸는 게 생각보다 많이 어려웠다.

그동안 DFS를 이용해 최단 거리나 백트래킹 위주 문제를 많이 풀다보니

처음 이 문제를 봤을 때

"주어진 정점과 간선을 통해 DFS로 탐색할 수 있는 모든 방문순서를 구해야하나?" 생각했다

 

그렇게 할 수도 있겠지만 그러면 시간초과할 것 같았다.

이 문제는 DFS의 방문 순서에대해 생각해보아야 해결 할 수 있다.

 

예제 입력을 갖고 생각해보자.

4
1 2
1 3
2 4
1 2 3 4

이렇게 주어졌을 때 그래프는 다음과 같다

 

백준 16964 그래프

 

DFS로 탐색 할 때 1번 노드에서 출발하면

2번, 3번 중 방문 순서를 택해야 한다.

 

2번을 먼저 방문하기로 택하면 

1 2 4 3 이렇게 탐색 하고

3번을 먼저 택하면 1 3 2 4 순서로 탐색하게 된다.

 

 

 

2번 노드와 3번 노드중 어떤 걸 먼저 탐색하게 해야 할까?

보통 일반적인 DFS나 BFS 문제에서는 어떤 노드를 먼저 탐색하게끔 문제를 만들지 않는다.

결과적으로 다 탐색한 뒤 어떤 결괏값을 갖는지를 많이 물어본다.

하지만 이 문제에서는 어떤 노드를 먼저 탐색할지 정해주는 과정이 필수적이다.

 

문제 입력 마지막 줄에 예상 DFS 탐색 순서를 준다.

만약 위처럼 1 2 3 4 이렇게 주어졌다면

우리는 깊이 우선 탐색을 할 때 2번 노드를 3번노드 보다 먼저 택해야한다.

 

만약 주어진 예상 DFS 탐색 순서가 1 3 2 4 라면

우리는 깊이 우선 탐색을 할 때 3번 노드를 2번노드 보다 먼저 택해야한다.

 

 

즉 마지막 예상 DFS 탐색 순서를 바탕으로해서

어떤 노드를 먼저 탐색해야할지 정해주고,

정해진 노드 탐색 순서를 바탕으로 DFS를 수행했을 때

예상 DFS 탐색 순서와 일치하는지 확인하는 문제이다.

 

노드간의 연결 관계를 인접리스트로 만들고,

인접리스트의 노드 순서를 정해진 노드 탐색 순서로 정렬한 뒤

깊이우선탐색을 실행해야 한다.

 

이해를 돕기 위해 다른 입력으로 생각해보자

(마지막 줄, DFS예상 탐색 순서만 다르다)

4
1 2
1 3
2 4
1 3 2 4

 

order

1	2	3	4
1	3	2	4

1,2,3,4 노드가 있을 때

항상 탐색 순서는

1번 노드가 첫번째

3번 노드가 두번째

2번 노드가 세번째

4번 노드가 네번째로 돌아야한다.

 

이를 위해 order 배열에 순서에 해당하는 노드를 저장해준다

order[2] = 3이면 우선 순위 두번째 노드가 3이라는 뜻이다.

 

그리고 이런 우선순위를 바탕으로 인접리스트의 노드들을 정렬해준다.

 

 

각 노드의 탐색 우선순위를 지정해주기 위한 코드다.

bool comp(int a, int b){
	return order[a] < order[b];
}
    
for(int i=1; i<=n; i++){
	int node;
	cin >> node; 
	given_path[i] = node;
	order[node] = i;
}
	
for(int i=1; i<=n; i++){
	sort(ad[i].begin(), ad[i].end(), comp);
}

 

sort를 시행하기 전

1번 노드는 2번 노드를 먼저 탐색한다.

출발	연결된 노드 (순서)
ad[1] 1번노드	2, 3
ad[2] 2번노드	1, 4
ad[3] 3번노드	1
ad[4] 4번노드	2

 

 

sort 한 후 3번이 2번보다 우선순위가 높기 때문에 2 앞으로 온다.

이제 DFS를 돌면 2보다 먼저 탐색된다.

출발	연결된 노드 (순서)
ad[1] 1번노드	3, 2
ad[2] 2번노드	1, 4
ad[3] 3번노드	1
ad[4] 4번노드	2

다시 설명하자면,

이렇게 해주는 이유는

문제 입력에서 1,3,2,4 순으로 탐색을 할 수 있는지 물어보았기 때문에 3은 무조건 2보다 먼저 탐색되야한다.

 

문제입력에 주어진 조건을 바탕으로 

각 노드마다 우선순위를 적용해준 뒤 탐색한 후 1,3,2,4 순으로 탐색이 되는지 확인하기 위함이다.

 

 

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

vector<int> ad[100001]; 
int order[100001], given_path[100001], DFS_path[100001], L=1;
bool ch[100001];

bool comp(int a, int b){
	return order[a] < order[b];
}

void DFS(int x){
	ch[x] = 1;
	DFS_path[L++] = x;
	
	for(int i=0; i<ad[x].size();i++){
		int nx = ad[x][i];
		if(ch[nx]==0) DFS(nx);
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	
	for(int i=1; i<n; i++){
		int node1, node2;
		cin >> node1 >> node2;
		ad[node1].push_back(node2);
		ad[node2].push_back(node1);
	}
	
	// 각 노드마다 순서를 정해준다  
	for(int i=1; i<=n; i++){
		int node;
		cin >> node; 
		given_path[i] = node;
		order[node] = i;
	}
	
	for(int i=1; i<=n; i++){
		sort(ad[i].begin(), ad[i].end(), comp);
	}
	
	//1번부터 돌기 떄문  
	DFS(1);
	for(int i=1; i<=n; i++){
		if(given_path[i]!=DFS_path[i]){
			cout << 0;
			return 0;
		}
	}
	cout << 1;
	
	
}

백준 16964 메모리 , 시간

배열 대신 벡터로 동적으로 배열을 이용하면

메모리를 절약할 수 있겠지만 귀찮은 관계로 대부분 배열을 이용했다.

아마 인접리스트를 이용하지 않고 인접행렬[nxn]그래프를 이용하면 메모리 초과가 될 것이다.

 

인접리스트 알아보기