[알고리즘] 정올 1238 번 문제 : 미로 탈출 중간 단계

알고리즘 시험을 준비하면서 풀었던 문제들을 하나씩 소개하려고 합니다.

응용 문제까지 풀기위해서는 하나에 대해서 확실하게 이해하고 풀수 있는지가 중요하다고 봅니다.

 

1. 문제 이해

문제 제목과 같이 미로찾기 문제이고 이동할 수 있는 최대 거리를 구해야 합니다.

이동한 지점에서 각 방향으로 가능한 경로를 확인하면서 탐색해봐야 할 것 같습니다.

 

문제는 아래에서 확인하시고 충분히 읽어보시길 바랍니다.

정올 1238 문제

JUNGOL

1. 전역변수 선언

입력을 받아 사용하기 위해 전역으로 선언

int maze[MAX][MAX];  //! 입력된 미로 Map 저장
int visit[MAX][MAX]; //! 방문한 지점 저장
int dir[4];          //! 방향 정보 저장
int dx[5] = { 99, 0, -1, 0, 1 };
int dy[5] = { 99, 1, 0, -1, 0 };

2. 경로 확인 함수

이동할 Next 지점이 지도에서 갈 수 있는지 Check

//! 0 : out of range, 1 : ok
int CheckNext(int new_i, int new_j, int limit)
{
    //! within range
    if ((0 <= new_i) && (new_i < limit) && (0 <= new_j) && (new_j < limit)) {
        if (1 != maze[new_i][new_j])
            return 1;
    }
    return 0;
}

3. 방향별 탐색

Queue 를 사용한 BFS 로 탐색, 각 지점에서는 최대 4방향에 대해서 탐색합니다.

방향 전환 순서가 입력으로 주어지는 부분이 이 문제의 특징인 것 같습니다.

int doSearch(int limit)
{
    //! x, y
    queue <pair <int, int>> q; //! 좌표 형식으로 저장하기 위한 queue 선언
    int dist = 0;         //! 이동 거리 저장
    int dir_idx = 0;      //! 방향 변경 index
    int dir_val = dir[0]; //! 현재 방향

    q.emplace(make_pair(0, 0));

    while (!q.empty()) { //! queue 가 비어있다면 더이상 이동이 불가능하다.
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        if( 0 == visit[i][j] ) { //! 방문하지 않은 곳인지 확인
            visit[i][j] = 1;     //! 방문한 곳으로 표시
            dist++;              //! 이동거리 증가
        }
        else {
            break; //! 방문했으니 빠져나감
        }

        //! 현재 위치에서 4 방향으로 탐색을 시도
        for (int k = 0; k < 4; k++) {
            int new_i = i + dy[dir_val];              //! 새로운 x 좌표 설정
            int new_j = j + dx[dir_val];              //! 새로운 y 좌표 설정
            int ret = CheckNext(new_i, new_j, limit); //! 새로운 자표로 이동이 가능한 지 확인
            
            if (1 == ret ) { //! 이동 가능하므로 queue 저장 후 다음으로 
                q.emplace(make_pair(new_i, new_j));
                break;
            }
            else {           //! 이동 할 수 없다면 방향 전환
                dir_idx += 1;
                if (4 <= dir_idx) dir_idx = 0;

                dir_val = dir[dir_idx];
            }
        }
    }    
    return (dist-1); //! 시작지점 제외, 마지막까지 진행한 거리가 최대 거리가 된다.
}

4. 데이터 입출력과 탐색 함수 호출

마지막 부분은 데이터를 입력받고 위에서 작성한 함수를 호출해주는 main 함수입니다.

int main()
{
    //freopen("input.txt", "r", stdin); //! Test Input 용 코드
    
    //! Test Case 갯수 입력
    int N;
    scanf("%d ", &N);
    
    //! 미로 데이터 입력 : maze[][]
    
    //! 방향 정보 입력 : dir[]
    
    //! 탐색 함수 실행
    printf("%d\n", doSearch(N));
}

 

유사한 문제를 찾아 풀이하게 되면 내용을 추가하도록 하겠습니다.