미로 탐색

0. 참고 문헌

<뇌를 자극하는 알고리즘>

 

1. 개념

미로의 한 지점에서 탈출구로 향하는 경로 속에는 여러 길목이 있는데,

이들 각 길목에서 왼쪽으로 갈지, 오른쪽으로 갈지, 또 계속 가던 방향으로 계속 갈지의 물음(부분 문제)에 답(부분해)을 구하는 과정을 반복하면서 완성한 것이 탈출로(해) 이다.

여기에서 부분 문제의 답은 어느 것이라도 될 수 있다.

선택한 방향으로 끝까지 가봐야 '해를 이루는 부분해'가 될지 안될지를 알 수 있는 것이므로.

게다가 선택한 방향으로 가다 보면 새로운 갈래길목을 만나게 될 것이고,

그 곳에서도 또 여러 가능성을 두고 선택을 해야 하는 상황이 온다.

이렇게 해가 될 수 있는 가능성을 가진 부분해의 조합을 두고 후보해라고 한다.

백트래킹이 다루는 문제들은 대개 후보해의 수가 굉장히 많다는 특징이 있다.

이 속에서 해가 될 조건을 만족시키는 '진짜 해' 를 효율적으로 찾는 것이 백트래킹의 목적이다.

 

2. 설명

아래의 그림과 같은 미로에서 탈출로를 찾아야 한다고 가정해보자.

지금 S지점에 위치해 있으며, 탈출구가 있는 G지점까지 이동해야 한다.

길목에 붙인 번호는 갈래길목에서 나뉘어지는 길들을 구분하기 위해 매겨졌다.

길을 가다가 이 갈래길목을 만나면 어느 쪽으로 갈 것인가 선택해야 한다.

이 선택의 경우의 수를 트리로 나타낸 그림이 아래의 [그림 2] 이다.

[그림 1]

[그림 2]

출발점 S를 지나 만날 수 있는 새로운 길은 1번과 2번 두 가지이다.

1번 길의 끝에는 더 이상 새로운 길이 나오지 않고, 2번 길에는 3번과 4번으로 갈 수 있는 길목이 나온다.

3번 길을 가면 막다른 곳이 나오고 4번 길을 따라가면 5번과 6번을 선택할 수 있는 길목이 나온다.

5번 길에서는 새로운 길이 나오지 않고, 6번 길을 따라가면 목표지점인 탈출구 G를 만날 수 있다.

 

3. 미로 탐색 방법

미로를 탐색해 보자.

탐색 규칙은 아래와 같이 약속해보자.

1. 갈래 길이 나오면 무조건 왼쪽 길부터 들어간다.

2. 막다른 곳이 나오면 갈래 길목으로 되돌아 나와 그 다음 길을 시도 한다.

3. 1 ~ 2 과정을 목표 지점에 도달하거나 모든 경로를 다 탐색할 때까지 계속한다.

위의 규칙을 따라 미로를 탐색해 보면, 아래 그림과 같은 과정을 거쳐 S에서 G에 이르는 탈출로를 얻을 수 있다.

이 일련의 과정이 아래의 그림이다.

[step.1]

위의 step1에서는 갈래길이 나오면, 왼쪽 방향을 우선 시도한다고 했으므로 1번 길로 탐색을 시도한다.

 

[step.2]

 

step2에서 1번 길을 탐색 시도했는데 더 이상 갈 곳이 없음으로, 1번 길을 포기하고 오던 길로 되돌아간다.

 

[step.3]

step3에서는 2번 길로 탐색을 시도한다.

 

[step.4]

step4에서는 갈래길이 나오면, 왼쪽 방향을 우선 시도한다고 했으므로 4번 길을 탐색한다.

 

[step.5]

step5에서는 갈래길이 나오면, 왼쪽 방향을 우선 시도한다고 했으므로 5번 길을 탐색한다.

 

[step.6]

step6에서 5번 길을 탐색 시도했는데 더 이상 갈 곳이 없음으로, 5번 길을 포기하고 오던 길로 되돌아간다.

 

[step.7]

step7에서는 6번 길로 탐색을 시도한다.

 

[step.8]

step8에서는 갈래길이 나오면, 왼쪽 방향을 우선 시도한다고 했으므로 G로 탐색한다.

 

이런 step과정을 반복한 끝에 목적지를 찾게 된다.

S - 2 - 4 - 6 - G 가 이 미로의 탈출로라는 것을 알아 냈다.

 

위 과정은 깊이 우선 탐색 알고리즘과 많이 비슷하다.

DFS가 모든 노드를 방문하는 것이 목적이고, 백트래킹은 해를 찾는 것이 목적이기 때문에

꼭 모든 노드를 방문할 필요가 없다는 것이 둘의 차이점이다.

백트래킹은 해를 찾는 비용을 줄이기 위해 최대한 방문할 노드의 수를 최소화하는 것이 중요하다.

 

백트래킹이 다루는 문제들은 다양한 후보해를 갖고 있는데, 이 후보해들은 부분해로 이루어져있어서

위에서 설명한 미로 문제에서와 같이 트리 형태로 표현할 수 있다.

이러한 후보해 속에서 해를 찾아가는 과정은 아래와 같다.

(1). 해를 찾아가는 과정은 '루트' 에서부터 출발한다. (루트도 하나의 부분해이다.)

(2). 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻는다.

(3). 2에서 얻은 목록의 부분해들을 하나씩 방문한다.

(4). 방문한 부분해가 요구하는 조건을 만족시키면 그 자리에서 2번 3번 과정을 수행하고,

      그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도한다.

(5). 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없음을 확인했을 때까지,

      2 ~ 4번 과정을 반복한다.

위에서 해를 구하는 함수는 아래와 같다.

 

4. 구현

< point.h >

< main.c >

< MazeInfo.h >

< MazeInfo.c >

프로그램 실행결과

5. 헤더 파일 & 소스 파일

point.h

0.00MB

main.c

0.00MB

MazeInfo.h

0.00MB

MazeInfo.c

0.00MB

 

아래의 방식은 자료 구조stack을 활용해서 구현한 미로 탐색이다.

designatedroom87.tistory.com/111?category=868809

스택의 활용 - 미로 탐색