[자료구조] 스택을 이용해 미로 탐색하기

6x6 미로

위와 같은 6x6의 미로가 있을 때 도착 지점(4,5)까지 미로를 탐색하는 알고리즘은 다음과 같습니다.

1. 현재 위치에서 이동이 가능한 칸들의 위치를 위, 아래, 왼쪽, 오른쪽의 순서로 스택에 저장합니다.
2. 스택의 top 위치로 이동합니다.
3. 위 과정을 반복합니다.
4. 이동 가능한 위치를 모두 검사했거나, 현재의 위치가 도착 지점의 위치와 같다면 중단합니다.

 

 

스택을 이용한 미로 탐색

 

 

// 멤버 변수들
POINT m_MyPos;		// 현재 내 위치
std::stack<POINT> m_MovableStack;	// 이동가능한 곳의 스택
bool m_IsEnd;		// 도착 지점인지
enum class eMapAttr
{
	S,	// 시작 지점
    O,	// 이동 가능
	X,	// 이동 불가능 (벽)
    E,	// 도착 지점
}


// 스택에 원소가 있다면 (이동가능한 곳이 있다면)
// 내 위치를 다음 위치(top)로 변경
if (!m_MovableStack.empty())
{
    m_MyPos = m_MovableStack.top();
    m_MovableStack.pop();
}

// 도착 지점인지
if (map[m_MyPos.x][m_MyPos.y] == eMapAttr::E)
{
    m_IsEnd = true;
}

// 상, 하, 좌, 우 탐색
for (int i = 0; i < 4; i++)
{
    POINT nowPos = m_MyPos;

    switch (i)
    {
    case eDir::Top:
        nowPos.y--;
        break;
    case eDir::Down:
        nowPos.y++;
        break;
    case eDir::Left:
        nowPos.x--;
        break;
    case eDir::Right:
        nowPos.x++;
        break;
    }

    // 배열에서 벗어난 인덱스일 경우 이동 불가능
    if (nowPos.x < 0 || nowPos.y < 0)
        continue;

    // 이전에 갔던 곳인지 체크한다.
    bool check = CheckAttr(nowPos);

    // 이전에 갔던 곳 또는 벽이라면 이동 불가능하다.
    if (check || map[nowPos.x][nowPos.y] == eMapAttr::X)
        continue;
	
    // nowPos는 이동가능한 곳이다. 스택에 push
    m_MovableStack.push(nowPos);
}

 

 

 

참고

• C언어로 쉽게 풀어쓴 자료구조