자료구조: Stack & Queue (3)

오늘은 지난번에 이어서 미로찾기 문제를 Queue를 이용해서 푸는 방법을 알아보겠다.

Map 하고 i,j는 지난번 방법과 같다.

다만 지난번 방법하고 다르게 가까운데를 먼저 가보게끔 구현을 하게된다. 

이러한 BFS 의 특징중에 하나는 제일 짧은 길을 찾을 수 있다는 것이다. 

코드는 다음과 같은 형식을 가지게 된다.

BFS 명시적 Queue

int Map[M][N];
int i, j;
 
int Find()
{
    QueueInsert(0, 0);
    while( ){
        ( i, j ) = QueueDelete() //방문하기 직전, Queue가 Empty이면 실패
        //Map[i][j] == 0인 경우만
        Map[i][j] = '*'; //목적지 확인
        // (i, j+1), (i, j-1), (i+1, j), (i-1, j)중 0인 좌표를 queue에 Insert
  
   }
}