Recursion - 미로 찾기

미로 찾기

미로 찾기에는 여러가지 유형들이 있겠지만 목적지가 설정된 미로에서

주어진 좌표를 시작점으로 목적지까지 도달할 수 있는지 없는지 boolean값을 반환하는 함수를 만들려고한다

접근 방법

역시 알고리즘의 알자도 모르는 나 답게 어떻게 재귀적으로 접근하는지 모르겠어서 한번 봤다

내가 있는 현재 위치가 목적지인지 검사하고 그렇지 않으면 인접한 길로 간다

인접한 길로 넘어간 뒤에 다시 내 위치가 목적지인지 검사하고 그렇지 않으면 인접한 길로 간다..

즉 처음에 넘겨준 좌표에서 좌표값만 수정해서 재귀 호출을 하면 되는 것이었는데

앞으로는 그냥 모르겠다고 할 것이 아니라 단계적으로 글을 써서 접근해 봐야할 듯 싶다

구현

const map = [[0,0,0,0],
             [0,0,0,0],
             [0,-2,0,0],
             [0,-2,0,1]];

const x=0,y=0;

우선 변수들을 초기화했다

map변수는 목적지 1과 지날 수 없는 벽인 -2를 가진 미로

x,y는 시작 좌표다

function findExit (x,y){
    if(x<0 || y<0 || x>=map.length || y>=map.length){
        return false;
    }
    if(map[x][y]===1)  {
        return true;
    }
    if(map[x][y]!==0){
        return false;
    }

    map[x][y] = -1;

    return findExit(x + 1, y) || findExit(x, y + 1) || findExit(x - 1, y) || findExit(x, y - 1);
}

함수 부분

     if(x<0 || y<0 || x>=map.length || y>=map.length){

x,y의 크기가 미로 밖을 넘어가는지 확인하고 넘어간다면 false를 반환하는 조건

    if(map[x][y]===1)  {

현재 나의 위치가 목적지라면 true를 반환하는 조건

    if(map[x][y]!==0){

내가 지나온 길이거나 벽이라면 false를 반환하는 조건

    map[x][y] = -1;

내가 지나온 길을 -1로 선언했다

    return findExit(x + 1, y) || findExit(x, y + 1) || findExit(x - 1, y) || findExit(x, y - 1);

여기가 재귀 호출을 하는 부분인데 좌표의 값을 하나씩 먼저 움직여 본 뒤에 위의 조건문들을 확인하고 목적지를 찾았으면 true를 반환한다