[자료구조] 미로 문제

미로 문제

maze는 1≤i≤m이고 1≤j≤p인 이차원 배열 maze[i][j]로 표현

1 - 막혀있음

0 - 통과 가능

 

현재의 위치

x: maze[i][j]

미로의 경계면에 있을 때 경계 조건을 매번 검사하는 것을 피하기 위해 미로의 주위를 1로 둘러쌈

배열은 maze[m+2][p+2]로 선언

현재 위치에서 가능한 이동

 

이동할 수 있는 방향들을 배열 move에 미리 정의

struct offsets
{
    int a, b;
};

enum directions {N, NE, E, SE, S, SW, W, NW}
offsets move[8];

q	move[q].a	move[q].b
N	-1	0
NE	-1	1
E	0	1
SE	1	1
S	1	0
SW	1	-1
W	0	-1
NW	-1	-1

 

세 배열 maze, mark, move 사용

• 새로운 3원소 쌍(i, j, dir)으로 표현
• 가장 최근에 입력된 3원소 쌍을 먼저 제거하므로 이 리스트는 스택

 

- Path 함수에서 배열 maze, mark, move 전역 변수로 가정

- stack은 items의 스택으로 정의

 

구현

struct Items
{
    int x, y, dir;
    Items(int i, int j, directions d)
    {
        x = i;
        y = j;
        dir = d;
    }
};

struct offsets
{
    int a, b;
};

enum directions {N, NE, E, SE, S, SW, W, NW};

int **maze, **mark;
// 배열 maze, mark, move 전역변수로 초기화
offsets move[8];
// 이동할 수 있는 방향들을 미리 정의하는 작업 필요
// 블로그 포스팅 위쪽의 표 참고

template <class T>
ostream &operator<<(ostream &os, Stack<T> &s)
{ // 미로를 이동한 경로 출력
    os << "top = " << s.top << endl;
    for (int i = 0; i <= s.top; i++)
        os << i << ":" << s.stack[i] << endl;
    return os;
}

ostream &operator<<(ostream &os, Items &item)
{
    return os << item.x << "," << item.y << "," << item.dir;
}

void Path(const int m, const int p)
{ // maze[0][i] = maze[m+1][i] = maze[j][0] = maze[j][p+1] = 1
  // 미로의 경계 부분 미리 초기화 필요
  // 0 <= i <= p+1, 0 <= j <= m+1

    mark[1][1] = 1; // (1,1)에서 시작
    Stack<Items> stack(m * p);
    Items temp(1, 1, E);
    // temp.x, temp.y, and temp.dir 초기화
    stack.Push(temp);
	// 여기까지 미로 입구 초기화, 동쪽 방향으로 탐색 시작하도록 초기화

    while (!stack.IsEmpty()) // 스택이 비어있지 않다면
    { // 잘못된 길로 갔으므로 다시 이동할 수 있을 때까지 스택 제거
        temp = stack.Top();
        stack.Pop();
        int i = temp.x;
        int j = temp.y;
        int d = temp.dir;
        while (d < 8) // 미로를 이동
        {
            int g = i + move[d].a;
            int h = j + move[d].b;
            if ((g == m) && (h == p))
            { // 마지막 칸 도착, 이동한 경로를 출력
                cout << stack;
                cout << i << " " << j << endl;
                cout << m << " " << p << endl;
                return;
            }
            if ((!maze[g][h]) && (!mark[g][h])) 
            { // 가능한 이동&&처음 도달하는 장소
                mark[g][h] = 1;
                // 이동한 공간 채우기
                temp.x = i;
                temp.y = j;
                temp.dir = d + 1;
                stack.Push(temp); // 이 위치를 스택에 push
                i = g;
                j = h;
                d = N; // (g,h)로 이동
            }
            else
                d++; // 다른 방향을 탐색
        }
    }
    cout << "No path in maze." << endl;
}

 

시간복잡도 - O(mp)