[알고리즘] 길 찾기 algorithm (bfs, dynamic programming, DP, 다이나믹 프로그래밍
미로 찾기 알고리즘을 소개합니다. 보통 dfs(depth first search)나 bfs(breadth first search)가 언급되기도 한데, 여기에는 dynamic programming (동적 프로그래밍, 동적 계획법) 중심으로 설명하며, 사실 이해하기 쉽지 않은 재귀(recursive) 호출도 사용하지 않습니다.
(물론 여기 보다 더 최적화된 코드도 있다는 것을 염두해 둡니다)
이 알고리즘의 중심은, LIST와 VISIT 입니다. (실제로 LIST를 QUEUE 개념과 유사하게 사용합니다. 즉 이것은 bfs 방식으로 진행된다는 것을 의미합니다.)
LIST에는, (x,y) 좌표와 이미 처리되었는지 flag가 포함됩니다.
임의의 지점에서 이동 가능한 동서남북 방향에서, 가능한 후보를 LIST에 추가합니다.
그리고 해당 추가할 때는 flag를 off합니다. 그리고, LIST에 항목을 하나 꺼내서 해당 지점의 동서남북을 체크한 뒤에는 flag를 on 시킵니다. 그리고, LIST에서 꺼낼때는 flag가 off인 것만 처리합니다.
VISIT은 동서남북을 체크하는 중심에 있는 좌표가 ON되는 배열입니다. 한번 방문한 지점은 다시 방문하지 않도록 하기 위한 방법입니다.
글이 길어졌는데, 위 LIST의 flag는 dynamic programming의 개념에 해당되고,
VISIT은 bfs의 개념에 해당됩니다.
(만일 LIST 대신 QUEUE를 사용했다면 자연스럽게 bfs개념만 사용한 경우가 됩니다.)
ooo..
.o...
.o..o
.oo.o
.oooo
와 같은 미로가 있다고 가정합니다. 붉은색 두점이 연결 가능한지 체크해 보도록 합시다.
마지막 부분의 c 코드를 실행하면 아래와 같은 결과가 출력됩니다.
왼쪽은 지도이며, 오른쪽은 VISIT 정보입니다.
전체 9번의 loop로 길을 찾음이 확인됩니다.
*는 현재 동서남북을 체크하고 있는 현재의 위치입니다.
iteration : 0 iteration : 1 iteration : 2 iteration : 3 iteration : 4 iteration : 5
iteration : 6 iteration : 7 iteration : 8 iteration : 9 <done> |
아래는 LIST를 활용한 동적 계쇡법(dynamic programming)으로 미로를 찾는 c코드 입니다.
참고로 만일, QUEUE를 사용했다면,
for (nListIndex=0; nListIndex<nCurListCount; nListIndex++) |
와 같은 불필요한 for-continue 수행이 제거됩니다. 만일 N이 5가 아닌 5,000이상의 큰 숫자가 들어오는 경우, 위 매번 중복된 for-continue가 수행될 수 있습니다. 그러니, 더 빠른 알고리즘을 원한다면, QUEUE를 사용해야 합니다. (사실, FRONT와 REAR 변수만 있다면 아래 코드에서 조금만 수정하여 QUEUE가 만들어 질 수 있습니다.)
// map.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
// 지도 data
// - 1은 이동 가능한 block
// - 0은 이동 불가능한 block
// - 1부터 시작하는 index를 사용하므로, 맨 윗줄과 맨 왼쪽줄은 사용하지 않는다.
// - 이동시에는 동서남북 방향만 가능하다.
#define MAP01 {{0,0,0,0,0,0}, \
{0,1,1,1,0,0}, \
{0,0,1,0,0,0}, \
{0,0,1,0,0,1}, \
{0,0,1,1,0,1}, \
{0,0,1,1,1,1}};
// ****************************************************************************
// * 문제 input
const int M = 101; // map의 최대 가로/세로 크기. 문제의 스펙으로 필요할 수 있다.
const int N = 5; // 현재 문제에 해당되는 map의 가로/세로 크기 (N < M-1)
int map[N+1][N+1] = MAP01; // 지도 배열
int A=1, B=1; // 지점1 (B, A) (c 2차원 배열은 y,x)
int C=5, D=5; // 지점2 (D, C) (c 2차원 배열은 y,x)
// ****************************************************************************
// * 문제 output
bool bConnected = false; // 지점1과 지점2가 연결되어 있느냐? 없느냐?
// ****************************************************************************
// * 문제 해결을 위한 변수, 함수 - 리스트 관련
typedef struct tagST_NODE
{
int i; // map[i][*]의 i 좌표
int j; // map[*][j]의 j 좌표
bool bProcessed; // 동서남북 이동 처리가 완료되었는지?
} ST_NODE, *LPST_NODE;
const int L = N*N; // 리스트의 개수는 좌표의 모든 항목을 포함할 정도로 크다.
ST_NODE stArrList[L]; // 리스트
int nListCount; // 리스트의 item 개수
int nListIndex; // 리스트 계산을 위한 변수
void ClearList(); // 리스트를 초기화한다.
void AppendList(int i, int j); // map[i][j]가 처리될 때, 리스트에 해당 좌표를 기록한다.
// ****************************************************************************
// * 문제 해결을 위한 변수, 함수 - visit 관련 (한번 방문 했는가?)
bool bVisit[N+1][N+1]; // bVisit[i][j] : true(방문했다) / false(방문하지 않았다)
void ClearVisit(); // visit 정보를 초기화한다.
// ****************************************************************************
// * 갈 수 있는 곳이 있는지? 더 이상 없었는지? 체크
bool bChanged; // false이면 더 이상 갈 수 없어, visit의 변경이 없었다는 뜻임
// ****************************************************************************
// * 디버깅 용도
int DEBUG_nIteration;
void DEBUG_print(int ii, int jj);
// 코드 시작
void ClearList()
{
nListCount = 0;
}
void AppendList(int i, int j)
{
if (nListCount >= L)
{
// list를 벗어남
return;
}
// 리스트에 항목 하나를 추가한다.
stArrList[nListCount].i = i;
stArrList[nListCount].j = j;
stArrList[nListCount].bProcessed = false;
nListCount++;
}
void ClearVisit()
{
int i = 0;
int j = 0;
for (i = 0; i <= N; i++)
{
for (j = 0; j <= N; j++)
{
bVisit[i][j] = false;
}
}
}
bool CalcConnect()
{
bool bRtnValue = false; // 연결할 수 없는 것을 기본값으로 두고 시작한다.
int nCurListCount = 0;
int i = 0;
int j = 0;
// 입력이 올바른지 검사한다.
// 범위가 벗어난 입력이 전달되어 오류를 잃으킬 수 있다.
if (N > M) goto FINAL;
if ((A <= 0) || (B <= 0) || (C <= 0) || (D <= 0)) goto FINAL; // 주어진 좌표 범위 체크 (최소 1이상이여야 한다)
if ((A > N) || (B > N) || (C > N) || (D > N)) goto FINAL; // 주어진 좌표 범위 체크
if ((map[B][A] == 0) || (map[D][C] == 0)) goto FINAL; // 주어진 좌표는 갈 수 있어야 한다. 즉, 1이여야 한다.
// 우선, 리스트에 시작점을 추가한다.
// C 언어의 2차원 배열은 i, j위치가 변경된다.
AppendList(B, A);
// 이제 한 block씩 이동하면서 목적지까지 갈 수 있는지 체크한다.
// 목적지까지 도착하거나,
// 더이상 움직일 곳이 없다면,
// 무한 loop는 종료된다.
for (;;)
{
// 아래 코드에서 bChange가 true가 될 수 있다.
// 일단, false로 만들어 줘서, true로 되는지 체크할 수 있도록 한다.
bChanged = false;
// 아래 코드에서, 리스트는 계속 추가되어 count가 증가된다.증가 되기 전의 현재 count를 가져온다.
nCurListCount = nListCount;
for (nListIndex=0; nListIndex<nCurListCount; nListIndex++)
{
// 리스트에 있는 항목중 한번이라도 처리되었다면 수행하지 않는다.
if (true == stArrList[nListIndex].bProcessed) continue;
// 한번도 처리되지 않은 위치라면, 이제 처리한다.
i = stArrList[nListIndex].i;
j = stArrList[nListIndex].j;
// 현재 좌표를 방문했다.
bVisit[i][j] = true;
// debug 용으로 정보 출력
DEBUG_print(i, j);
// 동서남북 방향으로,
// - map에서 갈 수 있고
// - 한번이라도 방문하지 않았다면,
// * 이동한 좌표를 리스트에 추가하고,
// * 방문 체크를 하고,
// * 한번이라도 옮겼기 때문에 변경 체크
// 를 한다.
if ((map[i-1][j] == 1) && (bVisit[i-1][j] == false) && (i-1>=1)) { AppendList(i-1, j); bVisit[i-1][j] = true; bChanged = true; }
if ((map[i+1][j] == 1) && (bVisit[i+1][j] == false) && (i+1<=N)) { AppendList(i+1, j); bVisit[i+1][j] = true; bChanged = true; }
if ((map[i][j-1] == 1) && (bVisit[i][j-1] == false) && (j-1>=1)) { AppendList(i, j-1); bVisit[i][j-1] = true; bChanged = true; }
if ((map[i][j+1] == 1) && (bVisit[i][j+1] == false) && (j+1<=N)) { AppendList(i, j+1); bVisit[i][j+1] = true; bChanged = true; }
// 동서남북을 이동했으니깐,
// [i][j] 좌표는 처리되었다. flag를 세팅하여,
// 다음번에는 또 동서남북 이동을 하지 않도록 한다.
stArrList[nListIndex].bProcessed = true;
// 2차원 배열은 i, j 뒤바뀐다.
if (bVisit[D][C] == true)
{
// 목적지에 드디어 방문했다.
bRtnValue = true;
goto FINAL;
}
}
if (bChanged == false)
{
// 만일, 위 for-loop에서
// 변경된 부분이 없다면, 더이상 갈 곳이 없다는 뜻이다.
// 이경우에는 종료한다.
break;
}
}
FINAL:
return bRtnValue;
}
void DEBUG_print(int ii, int jj)
{
int i = 0, j = 0, k = 0;
printf("\niteration : %d\n", DEBUG_nIteration);
for (i=1; i<=N; i++)
{
for (k=0; k<2; k++)
{
for (j=1; j<=N; j++)
{
if (k==0) printf("%c", map[i][j]==1?'o':'.');
else printf("%c", bVisit[i][j]==true?( (i==ii)&&(j==jj)?'*':'o' ):'.');
}
printf(" ");
}
printf("\n");
}
DEBUG_nIteration++;
}
int main()
{
bConnected = CalcConnect();
printf("\n<done>\n");
printf("- result : %d\n", bConnected);
printf("- iteration : %d\n", DEBUG_nIteration);
return 0;
}
|