도전! 초난문 최단거리 구하기

도전! 초난문이라는 스마트폰 게임이 있다. 하루에 한 문제씩 어려운 문제가 주어지고 이 문제를 풀면 되는 굉장히 심플한 게임이다. 문제의 룰도 간단하다. 위의 그림과 같은 8x8의 보드에서, 상하좌우 4방향으로 흰색 블록을 옮기는 과정을 반복하여 모든 흰색 블록이 검은 테두리의 회색 블록에 들어가게 하면 된다. 말로 설명하는 것보다 한 번 플레이해보는게 이해하기 쉬우니 궁금하신 분들은 다운로드 추천. 다운 받기 귀찮으시다면 아래 동영상을 한 번 해보시면 바로 어떤 룰의 게임인지 이해할 수 있을 것이다.

이 걸 몇 번 플레이하다가, 갑자기 최단거리를 찾아내는 프로그램을 만들고 싶어져서 한 번 그 프로그램을 만들어 보았다.

1. 접근 방법

처음의 접근 방법은 심플했다. '목표에 도달할 때까지 각 step별 경우의 수를 모두 확인해보자.'

모든 경우의 수를 빠르게 따져보려면 현재 게임 보드의 배치 상태를 효율적으로 관리해야하는데, 이 때 게임 보드의 전체 칸 수가 64칸이라는 것에 착안하여 long long int형 변수 하나에 현재 흰색 칸의 배치를 저장할 수 있을 거라고 보았다.

말하자면 위와 같이 64개 칸 각각에 1,2,3,4... 64로 번호를 붙이고, 특정 칸에 흰색 네모가 있으면 1, 아니면 0으로 비트를 구성하면 64비트 정수형 변수 하나에 모든 종류의 보드 상태를 다 저장할 수 있는 것이다. 예를 들어 4번 8번 칸에 흰색 사각형이 있으면 4,8번 비트를 각각 1로 두고, 나머지 비트는 0으로 하는 방식.

이렇게 해서 현재 흰색 사각형들의 배치 상태와, 목표로 하는 배치 상태를 각각 별도의 64비트형 정수로 설정하고, 두 값이 같아질 때까지(값이 같다는 것은 현재 상태와 목표 상태가 동일 배치라는 의미이므로) 계속해서 모든 경우의 수를 탐색하는 것이 처음의 접근 방식이었다.

간단히 기술하면 아래 과정을 반복하는 것이다.

1. 제일 처음의 배치 상태를 나타낸 숫자를 queue에 넣는다. step을 0으로 초기화 한다.

2. 이 시점에서 queue에 있는 모든 원소들에 대해, 상,하,좌,우 4방향으로 옮겼을 때 상태를 나타낸 숫자를 구한다. 이렇게 해서 구한 숫자가 이미 queue에 들어간 적이 있었다면, 이 원소는 이보다 이른 step에 도달한 적이 있었다는 의미이므로 더 이상 체크하지 않는다.(이미 queue에 들어간 적이 있었는지 여부는 따로 관리한다.)  그렇지 않다면 이 숫자를 queue에 집어넣는다.(다음 step에 검사해야할 후보이므로)

3. queue에 있는 원소를 꺼냈는데, 이 원소의 값이 목표 값과 똑같으면 해당 목표까지 도달하는 path와 step수를 출력하고 종료, 그렇지 않다면 step을 1증가시키고 3번 과정을 반복한다. 결과를 못 찾았는데 queue가 비었다면 경로가 존재하지 않는다는 의미.

굉장히 단순하고 무식한 접근법이다. 간단히 생각해서 step이 1늘어날 때마다 상,하,좌,우 4가지 서로다른 상태가 생기므로 최소 스텝 수가 s일 때 4의 s제곱만큼 경우의 수가 늘어나므로 굉장히 비효율적이다.(물론 이미 방문했던 형태는 제외하므로 실제로 이거보다는 훨씬 빠름) 따지자면 너비우선탐색(BFS - Breadth-first search) 방식으로 같은 레벨의 모든 케이스를 다 순회해 보는 것이다.

아무튼 이런 비효율적인 방법을 써도 꽤 많은 문제가 풀리긴 풀린다. 아래는 샘플로 돌린 자료들.

2014년 11월 28일자 문제

이 입력에 대해 위 방법을 써서 거의 0.1초 안에 답이 나온다.

결과:

move : 0, case : 1

move : 1, case : 4

move : 2, case : 8

move : 3, case : 16

move : 4, case : 40

move : 5, case : 74

move : 6, case : 120

move : 7, case : 178

move : 8, case : 274

move : 9, case : 422

move : 10, case : 627

move : 11, case : 828

move : 12, case : 1084

move : 13, case : 1368

move : 14, case : 1533

move : 15, case : 1646

move : 16, case : 1763

move : 17, case : 2068

move : 18, case : 2289

move : 19, case : 2672

move : 20, case : 3034

move : 21, case : 3485

move : 22, case : 3844

move : 23, case : 4067

LLULRDDDLUURRUUDRDRDRDD

23단계 가는 동안 케이스가 4067개 까지밖에 증가하지 않았다. 아무래도 형태상 흰색 사각형들이 여러 가지 경우의 수가 나오기 적합한 형태가 아니기 때문에 중복된 형태들이 많이 걸러내지지 않았을까 싶음.

2014년 11월 30일자 문제

이 문제의 수행 결과는 다음과 같다.

move : 0, case : 1

move : 1, case : 2

move : 2, case : 8

move : 3, case : 26

move : 4, case : 79

move : 5, case : 229

move : 6, case : 604

move : 7, case : 1547

move : 8, case : 3764

move : 9, case : 8436

move : 10, case : 16936

move : 11, case : 29622

move : 12, case : 44738

move : 13, case : 59936

move : 14, case : 72407

move : 15, case : 79148

move : 16, case : 79509

move : 17, case : 74180

move : 18, case : 64470

DRUDRDLLLLUUDDLLRD

이 문제도 생각보다 case가 그리 많지 않음. 그리고 왠만한 문제들은 이것처럼 BFS로도 그닥 어렵지 않게 풀린다.

그런데...

11월 29일자 문제

이 문제가 진짜 문제였다. 하루밤 내도록 돌렸는데도 경우의 수가 너무 많아 결과를 내지 못했다. 한 12스텝쯤 가면 case가 200만 가지 정도를 넘어서게 되고, 15스텝쯤 되면 메모리를 9GB정도 잡아먹는다.

그래서... 아무래도 BFS식으로 다 따지는 건 역시 답도 없다는 생각이 들어서 한 번 DFS(Depth-first search)로 접근해보자고 마음먹었다.

2. DFS 방식의 접근 

 말하자면 모든 경로를 순차적으로 다 구해보되, '최단 경로일리가 없는 경로'들을 미리 가지치기해서 경우의 수를 줄여보자는 식의 접근법이다. 그런데 이 방식으로 접근하려고 하니 처음 문제가, 일단 경로를 하나 찾아야 걔를 기준으로 최단 경로보다 긴 애들을 가지치기 할 지 어떨지 결정을 할 수가 있는데, 이게 워낙 경우의 수가 다양하다보니 첫 번째 경로를 찾는 것 자체가 너무 오랜시간이 걸려버렸다. 그래서 하나의 가정을 두고 그 위에서 DFS로 접근하기로 했다.

 말하자면, '최단 경로는 길어야 64 이내일 것이다' 라는 가정이다. 그래서 그냥 64 이상으로 전개되는 경로들은 일단 다 잘랐다. 64로 정한 이유는 대충 전체 보드 칸 수가 64칸이므로 아무리 움직여도 그 안에서는 해결되지 않을까하는 것이 첫번째였고, 내가 BFS로 돌려본 데이터중에 최단 경로의 길이가 25를 넘는 게 하나도 없었다는 것이 둘째였다. 아무튼 일단 64 넘는 건 다 자르고 그 아래에서 처리하다가 나중엔 32로 줄였다. 생각해보니 맨 왼쪽 위에 있는 애를 맨 오른쪽 아래까지 보내는데 14번이면 충분한데, 32번이면 대충 가능하지 않을까? 싶었다. 물론 별 근거는 없지만 경험상 대충 가능할 거라고 봄. 수학적으로 증명하고 싶지만 실력도 여백도 부족하여 생략.

아무튼, 일단 이렇게 생각하고 BFS랑 거의 똑같이 무식하게 돌렸다. 모든 경로를 다 체크하면서(목표 지점에 도착하거나 더이상 최단 거리일 가망이 없을 때까지 계속 한 경로로 탐색), 더 빨리 같은 상태에 도달한 적이 있거나, 내가 아는 최단 거리보다 이미 경로의 길이가 더 길어져 버렸다면 탐색을 중단하는 방식으로.

이렇게 하니까 어찌보면 당연한거지만 일단 BFS보다 느렸다. 당연히 29일자 문제의 답도 못구했고.. 그래서 이것보다 좀 더 가지치기를 해야 할 필요성을 느꼈다.

3. 가지치기 - 못해도 이것보단 오래 걸리겠지.

 가지치기에서 제일 중요한 건 '내가 알고 있는 최단 거리' 이내에 목표 지점에 도달할 가능성이 없는 놈들은 일찌감치 탐색을 중단해야한다는 것이다. 평균적으로 1스텝정도만 일찍 탐색을 중단해도, 경우의 수가 거의 4분의 1로 줄어들기 때문에 이런 조합 탐색 문제에서는 경우의 수를 최대한 빨리 잘라내는게 중요하다.

 어쨌든 내가 첫번째로 떠올린 방식은 현재 위치에서 목표 지점까지의 '수학적인 최소한의 거리'를 반영하는 것이었다. 

위 그림에서 1,2,3,4가 내가 목표지점까지 옮겨야 하는 흰색 블록, 노란색이 목표 지점이라고 하자. 1번 블록을 노란색 지점에 포함되도록 하려면 이 상태에서 최소한 5번은 움직여야한다.(RRRDD든 DDRRR이든 어쨌든... 직관적으로 알 수 있을 듯). 

 마찬가지로 2번 블록은 3번, 3번 블록은 3번, 4번 블록은 2번은 움직여야 목표지점에 도달할 수 있는데, 우리의 목표는 모든 흰색 블록을 노란색 목표지점에 넣는 것이기 때문에 이 상태에서 목표지점에 모든 흰색 블록을 집어넣기 위해서는 최소한 5번을 더 움직여야한다. 왜냐하면 1,2,3,4번 블록이 각각 5,3,3,2번은 움직여야 목표지점에 도달가능한데, 모두 집어넣어야하므로 1번 블록이 도달하기 위한 5번 이상은 움직여야할 것이 자명하기 때문이다.

그래서 위와 같은 논리로, 현 상태에서 목표 지점까지 도달 가능한 이상적인 최단 거리를 구한다음, 내 현재 경로의 길이와 이 값을 더한 값이 최단 경로의 길이보다 짧다면 탐색을 중단하는 것이다. 이상적인 최단 거리만에 도달가능하다고 가정해도 목표에 도달할 때까지 내가 알고 있는 최단 경로의 길이보다 더 오랜 시간이 걸리니까. 이런 경우를 제외하면 일단 꽤 많이 빨라진다. 근데 그래도 29일자 문제를 풀 지 못한다.

 좀 더 가지치기를 할 방법이 없을까. 고민하던 와중에 위에서 언급한 가지치기 방식을 조금 더 업그레이드 시킬 수 있을 거란 생각이 들었다. 말하자면, 이상적인 최단 거리를 구하되, '장애물'까지 고려한 최단 거리를 구하자는 것이다. 

목표 지점은 노란색, 장애물은 검은색, 나머지 숫자들은 해당 칸에서 노란색까지 도달하는데 필요한 최소 이동 횟수다. 단순히 목표 지점에서 시작해 확장해 나가면서 이 거리를 구할 수 있고, 이걸 테이블에서 저장해놓은 다음 참조하면 O(1)만에 값을 얻을 수 있으므로 연산도 빠르다. 어떻게 저 거리가 나왔는지는 숫자를 차근차근 따라가면 쉽게 이해할 수 있을 것이니 넘어가고, 이 값이 아무래도 위에서 제시한 단순 덧셈 최단 거리보다는 조금 더 큰 값이 나오기 때문에, 가지치기를 좀 더 할 수 있다. 정확히 계산은 못하겠지만 아마 평균적으로 1스텝 정도는 더 줄어들 것이다.

그리고 이 방법까지 적용하면 일단 11월 29일자 문제를 풀 수 있다!! 11월 29일자 문제의 해답은 아래와 같다.

move : 31, path : RULUURRLULURRDRDDDURRUUDDDLLDRR

move : 30, path : RULUURRLULUDDRURDRDDRDURDRDLDR

move : 29, path : RULUURRLULDDRURDRDDRDURDRDLDR

move : 28, path : RULUURRLURDDDDRDRDLDDRDDDURD

move : 27, path : RULUURRLUDRRDDRRDDURRDLLDRR

move : 26, path : RULUURRLDRRDRDRDURDRDLLDRR

move : 25, path : RULUURRDDDDRDRDLDDRDDDURD

move : 24, path : RULURRDDDDRDRDLDDRDDDURD

move : 23, path : RULURDRLDRDDRRLDRDDRURD

move : 22, path : RULRDRLDRDDRRLDRDDRURD

move : 21, path : RUDRDDDRRLDLRRDDDRURD

move : 20, path : RDRRRDRDDURDRRLDLRDR

move : 19, path : RDRRDRDRDURDRDLLDRR

그러나 문제는... 이 문제 푸는데 대충 10분 정도의 시간이 걸린다. 풀긴 풀지만 좀 어거지라는 느낌을 지울 수가 없다. 가지치기를 할 방법이 좀 더 많이 있을 것 같지만... 생각해내기가 힘들어서 다른 방면의 최적화를 진행해보기로 했다.

4. 어떤 방향으로 먼저 탐색할까?

위 제시된 방법들은 모두 현재 경로에서 다음 위치를 선택할 때, 무조건 LURD(좌상우하) 순으로 탐색해 들어갔다. 그런데, 이 방향을 선택할 때 '최단 경로일 확률'이 높은 쪽을 우선적으로 선택하게 만들면 일단 내가 알고 있는 최단 경로의 값을 빨리 줄일 수 있고(경로를 좀 빨리 찾게 될테니까), 이 값이 빨리 줄어들게 되면 탐색해야할 범위가 줄어들기 때문에 수행 속도가 빨라질 것이다.

근데 어떤 방향이 가장 확률이 높을 것인가.. 이 부분은 사실 증명은 못 하겠고 반쯤 경험에 의거한 추측을 해보았다. 간단한 추측이다. '목표지점과 평균 거리가 가까운 쪽이 먼 쪽보다 확률이 높을 것이다.' 사실 좀 말도 되는게, 평균 거리가 높다는 말은 그만큼 평균적으로 좀 더 많이 움직여야 결과 위치까지 도달할 수 있다는 의미이므로 어느 정도는 확률이 높을 수 있다고 볼 수 있을 것이다.( 물론, 돌아가는 쪽이 결과적으로는 더 빨라질 수도 있긴 한데 대부분의 경우는 가까운 쪽으로 가는게 빠르고, 그보다 원래 내가 썼던 방식이 아무 근거없이 4방향을 정했던 것이니만큼 원래 방식보다는 빨라질 것이다.)

아무튼 이 방식까지 적용하면 위 11월 29일자 문제의 답도 1~2분 이내에 구할 수 있다. 여전히 토나올만큼 시간이 오래 걸리지만 그래도 그럭저럭 쓸만한 수준은 됐다. 이 방식으로 답을 구하면 아래와 같이 나온다.

move : 31, path : RRUURRDRRRDDRDRRRLDLRDLLRDURDRR

move : 30, path : RRUURRDRRRDDRDRRDURRDDLLDLRRDR

move : 29, path : RRUURRDRRRDDRDRRDURRDLLDLRRDR

move : 28, path : RRUURRDRRRDDRDRRLDDLLRDURDRR

move : 27, path : RRUURRDRRRDDRDRDURRDLLLDRRR

move : 26, path : RRUURRDRRRDRRRDLDRLDDRRURD

move : 25, path : RRUURRDRRDRRRDLDRLDDRRURD

move : 24, path : RRUURRDRDRRRDLDRLDDRRURD

move : 23, path : RRUURLDRDDDRRLDDRDDDURD

move : 22, path : RRUUDDRRDRDLDLLRDRRURD

move : 21, path : RRDRDRDURDDRRDLLLDRRR

move : 20, path : RDRRRDRDDURDRRDLLDRR

move : 19, path : RDRRDRDRDURDRDLLDRR

위와 비교해보면, 결과적인 답은 같지만 그 과정이 사뭇 다르다. 이 방식은 매번 현재 상태에서 가장 확률이 높을 것으로 추정되는 방향을 먼저 탐색하기 때문에 꽤 빠르게 최종 경로까지 도달한다.

일단 이 방식까지 적용하면 왠만한 문제들은 다 빠르게 풀어내는 것 같은데, 아직 오래 걸리는 문제는 3,4분정도까지 걸려서 좀 느리긴 하다. 가지치기를 더 잘하고 탐색 방향을 좀 더 잘 정하면 아마 훨씬 빨라질 수 있을 듯 싶지만, 이 놈의 뻘짓에 꽂히는 바람에 과제고 프로젝트고 너무 밀려버려서 일단 이건 이 정도 선에서 마무리하고, 여유가 생길 때 조금씩 더 다듬을 예정. 결국 화요일쯤부터 시작된 뻘짓을 거의 3일만에 가까스로 끝냈다. 무쓸모하지만 뭔가 뿌듯.

*추가. 맨 위 사진에 있는 저 두 문제가 진짜 어려운 문제다. 현재 상태에서 프로그램 돌리면 저 두문제는 답을 구할 때까지 대략 7,8분 정도의 시간이 걸림. 일단 답을 구한 결과로는 왼쪽 문제는 18스텝, 오른쪽 문제는 15스텝만에 정답 위치까지 도달할 수 있다.