[코드트리] 벽 짚고 미로 탈출하기 C++

문제

https://www.codetree.ai/missions/2/problems/escape-maze-with-wall-following?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획 세우기

문제에 주어진 케이스들을 조건문에 잘 쓰기만 하면 통과가 될 것 같았다.

나갈 수 없는 경우를 잘 생각하는 것이 중요한데, 해당 칸을 방문할 때마다 visited 배열을 1씩 증가시킨다.

10번 이상 방문한 칸이 있는 경우 빙글빙글 돌고 있다는 것이라고 생각했다.

 

풀이

너무 느리다...

 

#include <iostream>

using namespace std;
int n;
char map[101][101];
int visited[101][101];


bool IsPossible(){
    bool tooManyVisits = false, isLeft=false;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j]>5) tooManyVisits = true;
            if(map[i][j]=='.'&&visited[i][j]==0) isLeft=true;
        }
    }
    if(tooManyVisits) return false;
    else if(isLeft) return true;
    return false; // 전부 1이면 못 나감
}

int Play(int x, int y){
    // 우(0, 1) 상(-1,0) 좌(0,-1) 하(1,0)
    int dx[4]={0, -1, 0, 1};
    int dy[4]={1, 0, -1, 0};

    // 방향을 트는 데에는 시간이 걸리지 않고 한 번 이동하는 데에는 1초의 시간이 걸린다
    int dir=0, time =0, rotationCnt=0;

    bool isEscape=true;
    while (true){
        if(!IsPossible()){
            isEscape = false;
            break;
        }
        int nx=x+dx[dir];
        int ny=y+dy[dir];
        
        // 바라보고 있는 방향으로 이동하는 것이 가능하지 않은 경우
        if(map[nx][ny]=='#'){
        // 앞에 벽이 있으면 반시계 90도
            if(rotationCnt>=4){
                isEscape = false;
                break;
            }
            dir=(dir+1)%4;
            rotationCnt++;
            continue;
        }
        else{
            rotationCnt=0; // 한 자리에서 도는 경우가 아니니 초기화

            // 바로 앞이 격자 밖이라면 탈출
            if(nx<0 || nx>=n || ny<0 || ny>=n){
                time++;
                break;
            }
            
            //이동했을 때 오른쪽에 벽이 있는 경우
            if(map[nx+dx[(dir+3)%4]][ny+dy[(dir+3)%4]]=='#'){
                visited[x][y]++;
                x=nx;
                y=ny;
                time++;
            }
            else{
                // 오른쪽에 벽이 없으면 한 칸 이동 후 시계방향 90도 한 칸 이동
                visited[x][y]++;
                x=nx;
                y=ny;

                dir=(dir+3)%4;
                visited[x][y]++;
                x+=dx[dir];
                y+=dy[dir];
                time+=2;
            }
        }
    }
    if(isEscape) return time;
    return -1;
}

int main() {
    int x, y;
    cin >> n >> x >> y;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }

    cout << Play(x-1, y-1) <<'\n';
    
    return 0;
}

더 나은 풀이

문제를 푼 다음 해설을 보니 visited배열을 3차원으로 선언해 같은 방향으로 해당 좌표에 들어온 적이 있었을 경우 -1을 출력하도록 되어 있었다. 3차원 배열을 만들 생각을 못 했었어서 다음에는 저런 식으로도 한 번 코드를 짜봐야 겠다...