DFS, 백트래킹, 완전탐색의 관계 (BOJ 1405 미친 로봇)

[그림 출저 : idea-sketch.tistory.com/29

 

DFS는 본래 그래프를 탐색하는 방법으로, 스택 자료구조를 활용하여 깊은 곳을 우선해서 탐색한다.

실제로 구현할때는 보통 재귀함수 형태로 구현한다.

이는 컴퓨터가 여러 함수를 호출할 때 메모리의 스택 공간에 함수 정보를 적재하는데, 제일 마지막에 호출된 함수가 끝날 때 제일 먼저 나오는, 스택 자료구조의 FILO 구조와 동일한 방식으로 작동하기 때문에 그렇다.

 

백트래킹은, 문제 조건을 만족하지 못해서 답을 찾을 가능성이 없는 '막다른 길'에 도달했을때, 이전 상태로 돌아가서 (Back-track) 다른 경우의 수를 탐색하는 방법이다. 

굳이 탐색하지 않아도 되는 상황을 피함으로써 보다 빠르게 답을 찾을 수 있다.

idea-sketch.tistory.com/29

[알고리즘] 되추적(Backtracking)을 알아보자.

 

4-Queens 문제를 생각해보자. 

체스판 위에 4개의 Queen을, 서로가 서로의 경로를 막지 않도록 놓는 방법을 찾는 문제다.

여기서 우리는 여러가지 선택을 할 수 있다.

첫번째 퀸을 어디다 놓을지, 첫번째를 놓은 후 두번째를 어디다가 놓을지, ....

 

우리가 선택할 수 있는 경우의 수 조합을 트리로 나타내면 깊이 5의 방대한 트리가 된다.

맨 아래층의 각 leaf는 4개의 Queen을 놓는 한 가지의 경우를 나타낸다.

엄청나게 많은 leaf 중에 우리가 찾고 있는 답이 있을 것이다.

 

답을 어떻게 찾을 수 있을까? 

맨 처음 생각해볼 수 있는건 완전 탐색 (Brute Force)이다. 

이 경우에는 무조건 각 leaf를 모두 탐색하는 방법인데, leaf가 엄청나게 많으니 그만큼 시간이 오래 걸릴 것이다.

너무 오래 걸려서 기다리는게 의미가 없을지도 모른다.

 

 

그래서, 우리는 어떻게는 답을 찾는 최적의 방법이 필요하다.

솔직히 굳이 다 살펴볼 필요가 없다. 첫번째 퀸을 놓고, 두번째 퀸을 겹치는 경로에 놓는 경우의 수는 벌써부터 틀렸다는 걸 알 수 있다.

완전 탐색은 이런걸 고려하지 않고 무조건 leaf를 모두 뒤지겠지만, 우린 여기서 이 경우의 수를 컷하고, 이전 상태로 돌아가 다른 수를 찾아보는게 낫다. (가지치기)

이게 백트래킹 (Back-tracking).

 

 

그럼 DFS는 뭐야?

맨 처음 설명했다시피, 그냥 그래프를 탐색하는 방법이다. 

트리도 그래프의 한 종류로 볼 수 있으므로, 당연히 트리도 DFS로 탐색할 수 있다. (leaf 까지 뒤지는데 우선적으로 중점을 두는 방식)

따라서, 완전 탐색이나 백트래킹 모두 DFS로 구현 가능하다.

별다른 조건을 넣지 않으면 DFS가 알아서 모든 트리를 뒤져줄테니 완전탐색이 되는 것이고,

다음 탐색을 진행하기 전, 해당 경우의 수가 문제 조건에 맞는지, 아직 적절한지 판단해서 아니라면 쳐내는 조건을 구현하면 백트래킹이 되는 것 (쉽게 말해, 스택에 넣기 전에 validity를 체크한다).

---

미친 로봇 문제를 풀며, 백트래킹을 구현하고자 했지만, 완전 탐색을 구현해버린 경우를 소개하고자 한다.

미친 로봇 문제의 포인트는, 로봇이 사이클 (이미 방문했던 곳에 다시 방문하는 것) 을 만드는 경우를 어떻게 파악하느냐다.

 

나는 테스트케이스들을 쭉 써보며, 다음과 같은 규칙을 찾아냈다.

각 방향은 반대 방향이 나왔을때 서로 상쇄된다고 하자. 예를 들면, S가 (0,-1)이고, N가 (0,1) 이므로, 둘이 더하면 (0,0)이 되는 개념.

로봇이 가야할 방향을 쭉 나열할 때 (ex. EEESSENNWWW), 어느 시점부터 방향의 합이 0이 되는 순간이 존재하면, 그때가 사이클이 형성됬을때임을 알 수 있다.

따라서 호출한 child 함수 B 에서 cycle이 형성되는지 알기 위해선, 이전에 호출된 어떤 parent 함수 A를 시작점으로 잡고, A와 B 사이에 움직인 방향들의 합이 0이 되는지 체크하면 된다.

어디를 시작지점으로 잡느냐에 따라 cycle이 형성되느냐 마느냐가 결정되는 만큼, 시작지점을 정하는게 중요하다.

그러므로, B 이전에 호출된 parent 함수들을 모두 한번씩은 시작지점으로 가정하고 합이 0이 되는지 체크해야겠다고 생각했고, 이게 복잡하다고 생각했다.

 

당시 나는 매번 child 함수를 호출해서 cycle 여부를 판별하기 위해, 앞서 등장한 parent 함수들을 모두 체크해야한다는 이 방법이 매우 비효율적이라고 생각했고 구현할 시도조차 하지 않았다.

그래도 합이 0이 되는걸로 사이클을 판단하는 아이디어 자체는 맞다고 생각했기에, 다른 구현 방식을 생각해보았다.

맨 말단 child 함수에서는 자신의 움직임(=방향)을 나타내는 pair를 반환한다.

그럼 그 child 함수를 호출한 바로 위 parent 함수는, 받은 값을 자신의 움직임에 더해서 0이 되는지 체크한다.

 

즉, child에서 사이클을 판별하는게 아니라, parent에서 사이클을 판별하도록 만들었다.

 for (int next_dir = 0; next_dir < 4; next_dir++) {
   pii next_moves = DFS(cnt + 1, next_dir); // 일단 child 함수 호출
   /*
   ▲
   일단 다음 위치 DFS 불러놓고, 그 결과로 나오는 움직임 pair를 현재에 반영시켜 지금이 cycle 시작점인지 판단하는 것.
   기교는 좋으나, cnt가 N이 되기 전에 cycle이 나타나면, 그 시점에 return을 안하기 때문에 무시당함.
   */

  // child에서 반환해준 방향합을 자기 자신의 방향에 더해서 사이클 판별
  current_move.first += next_moves.first;
  current_move.second += next_moves.second;

  // child 까지의 방향 합이 0이 되는지 체크. 맞다면 cycle count 올리기
  if (current_move.first == 0 && current_move.second == 0)
  global_cnt++;

  // 다른 방향 DFS를 위해 reset
  current_move.first -= next_moves.first;
  current_move.second -= next_moves.second;
}

 

실제로 구현해서 돌려보니, TLE가 뜨더라. 

왜? 이건 모든 경우의 수를 다 둘러보는 완전탐색 방식이니까.

 

문제점 1. 일단 반환 조건이 N번 탐색했을때다. N번 움직임에 도달하기 전에 cycle 발생하면 detect 할 수가 없다.

위에서 그림으로 설명한 예시도, 맨 마지막에 도달하기 전, 중간 부분에서 cycle 발생하잖아?

pii DFS(int cnt, int dir) {
  if (cnt == N)
  return direction[dir]; // ◀ 이러면 무조건 길이 N 될때까지 탐색하지 않냐??

  ...
}

문제점 2. 일단 child 함수를 호출하는 것 부터가 잘못됬음.

이러면 우선 탐색하고 나중에 validity를 체크하기 때문에, 백트래킹이 아님.

백트래킹은 validity 체크하고, 아니다 싶으면 탐색을 포기하거든.

---

그럼 이 문제는 어떻게 해결할 수 있을까?

 

간단하다. 매 DFS 호출 시, 그 자리에서 바로 cycle detection (validity check)를 하고, 문제 없을때만 child DFS를 호출하는 것이다. 즉, parent에서 validity 체크를 하는게 아닌, 말단 child 함수가 호출될 때마다 즉각즉각 체크를 해주는 것.

 

또 아주 좋은 생각이 났는데, DFS 재귀호출시마다 현재까지의 방향기록을 넘겨주는 것이다. (string history)

그 방향기록을 맨 뒤에서부터 앞 방향으로 읽어나가다가 합이 0이 되는 지점이 오면, 그 구간에서 cycle이 발생했다는 것을 알 수 있다. (is_cycle 함수)

// Back-tracking DFS to find non-cycle routes
void DFS(int cnt, string& history, double prob) {
	if (cnt == N) {
		total += prob;
		return;
	}

	// E W S N (next call)
	for (int next_dir = 0; next_dir < 4; next_dir++) {
		string next_hist = history;
		next_hist.push_back(compass[next_dir]);

		if (is_cycle(next_hist)) // ★ (Back-tracking) Pre-check if next step forms a cycle
			continue;

		DFS(cnt + 1, next_hist, prob*probability[next_dir]);
	}
	return;
}


// Takes direction-history string (ex. EESWNSS) and searches backward to find any cycle
bool is_cycle(string& history) {
	int E = 0, W = 0, S = 0, N = 0;

	for (auto iter = history.crbegin(); iter != history.crend(); iter++) {
		char c = *iter;
		if (c == 'E')
			E++;
		else if (c == 'W')
			W++;
		else if (c == 'S')
			S++;
		else if (c == 'N')
			N++;
		else
			throw(invalid_argument("--Invalid direction detected--"));

		// Counting from backwards, needs both pairs to be matching to form a cycle
		if (E == W && S == N)
			return true;
	}

	return false;
}

위 코드를 보면, DFS가 호출될 시, 다음 child DFS를 호출하기 전 history에 다음 방향을 넣고 is_cycle로 사이클이 생기는지 판단한다. 만약 생기면 스킵하고 다음 방향으로 넘어가 반복한다.

 

이게 Back-tracking이지. 스택에 넣기 전에 validity를 체크하는.

구현도 깔끔하게 된 것 같고, 기존의 sum-0 detection 아이디어를 구현해서 좋다.

 

하루종일 고민했고, 이 글 쓰는데도 오래 걸렸지만, DFS와 백트래킹의 개념을 명확하게 정리할 수 있었던 것 같다. 

 

* 참고로, 위 문제는 simulation으로 아주 쉽게 풀 수 있다.

기존에 방문했던 위치를 다시 방문하는걸 파악하는 부분이 어려운건데, 그냥 world 만들어놓고 로봇을 직접 움직이면서 이미 방문했던 위치 다시 방문할때 cycle 여부를 파악할 수 있다.