백트래킹 (Back Tracking) 알고리즘 이해하기

하이 오늘은 백트래킹 알고리즘을 정리해두려고한다.

 

먼저 백트래킹 알고리즘을 알려면 DFS알고리즘을 정확하게 알고 있어한다. 혹시 DFS 에 대해 잘 모르겠다 싶으면 아래 링크를 차곰해서 보고 오자.

https://devkingdom.tistory.com/263

DFS (Depth-First Search) 알고리즘 정리

 

백트래킹 알고리즘은 dfs 알고리즘 방식으로 가장 깊은 레벨까지 가서 정답인지 체크하고 아니면 그노드의 부모로 돌아가서 다른 자식노드를 체크하고 이렇게 쭈우우우욱 들어갔다가 거꾸로 나오면서 다른 노드도 체크하는 그런 알고리즘이다. ㅎㅎㅎㅎ

 

내가 써놓고도 무슨말인지 모르겠다. 그래서 준비했다.

 

아래와 같은 방향성을 가진 그래프가 있다고 가정하자.

시작은 1에서 출발하고 5까지 갈수있는 모든 경우의 수는 몇개인지를 구해보자. 이때 우리는 back traking알고리즘을 활용할 수 있다.

 

시작은 1에서 한다고 했다. 1을 체크해주고 Root에 1을 표시해주자.

 

 

 

1다음으로 갈때 1은 자기자신이면서 이미 체크가 되어있으니 넘어가고 다음 자식 노드인 2를 체크한다. 2는 아직 방문항 상태도 아니고 갈수 있는 곳이니 체크해준다.

 

 

 

다음은 2에서 갈수 있는 자식노드를 검사한다. 1,2,3,4 모두 갈수가 없기에 갈수있는 상태인 5로가서 체크한다. 5까지 왔으니 우선 1 2 5 라는 경우가 하나 나왔다.

 

 

 

이제부터 백트랙킹이다. 

5가 2의 마지막 노드임으로 2로 돌아오면서 5의 체크를 해제한다. 

 

 

 

1로 돌아오고

 

 

2의 다음노드인 3을 검사한다.

 

 

 

그리고 3에서 접근할 수 있는 곳 중 가장 빠른 곳인 2번을체크한다.

 

 

그러고 또 2번의 자식노드 중 체크가 안되어있으면서 갈수 있는 곳을 검사한다. 그게 5니깐 또 1 3 2 5의 경우를 찾았다.

 

 

자 이 과정을 쭈우욱 반복하면 아래의 나의 발그림처럼 나올것이다.

 

자 대충은 이해가 되었나 모르겠다. 이게 바로 백트래킹 알고리즘이다.

 

소스코드로 구현하면 아래와 같다.

public class BackTracking {
	static int answer=0;
	static int[][] graph;
	static int[] check;
	public static void main(String args[]){
		BackTracking backTracking = new BackTracking();

		graph = new int[6][6];
		check = new int[6];
		graph[1][2] = 1;
		graph[1][3] = 1;
		graph[1][4] = 1;
		graph[2][5] = 1;
		graph[3][2] = 1;
		graph[3][4] = 1;
		graph[4][1] = 1;
		graph[4][2] = 1;
		graph[4][5] = 1;

		check[1] =1;
		backTracking.dfs(1);
		System.out.println(answer);
	}

	public void dfs(int v){
		if(v==5) answer++;
		else {
			for (int i = 1; i <= 5; i++) {
				if( graph[v][i] == 1 && check[i] ==0 ) {
					check[i] = 1;
					dfs(i);
					check[i] = 0;
				}
			}
		}
	}

}

 

그런데...! 여기서 우리가 그래프를 즈렇게 배열로 만들면 .... 그래프의 정점 갯수가 많아지면 많아질 수록... 탐색할때 메모리와 시간이 많이 낭비된다. 그래서 이를 개선하여 리스트로 그래프를 만들어 낼 수 있다.

 

import javax.sql.rowset.serial.SerialArray;
import java.util.ArrayList;

public class BackTracking {
	static int answer=0;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] check;
	public static void main(String args[]){
		BackTracking backTracking = new BackTracking();

		graph = new ArrayList<ArrayList<Integer>>();
		check = new int[6];

		//idx 가 0부터 시작하니깐 1~5까지 체크하기 위해 6개 생성
		for(int i=0; i<=5; i++) {
			graph.add(new ArrayList<Integer>());
		}

		graph.get(1).add(2);
		graph.get(1).add(3);
		graph.get(1).add(4);
		graph.get(2).add(5);
		graph.get(3).add(2);
		graph.get(3).add(4);
		graph.get(4).add(1);
		graph.get(4).add(2);
		graph.get(4).add(5);

		check[1] =1;
		backTracking.dfs(1);
		System.out.println(answer);
	}

	public void dfs(int v) {
		if (v == 5) answer++;
		else {
			for (int num : graph.get(v)) {
				if (check[num] == 0) {
					check[num] = 1;
					dfs(num);
					check[num] = 0;
				}
			}
		}
	}

}

끝.