[백준] 2178번 미로 탐색

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

---

문제 풀이

 해당 문제는 처음에 DFS로 시도하였다. 하지만 시간초과가 나왔다. 미로의 최대 크기는 100X100 사이즈이므로 DFS나 완전 탐색으로 풀이 할 경우 시간 초과가 뜬다.

 

이 후 BFS로 풀이를 하였다.

 

DFS는 queue의 현재 위치를 shift하여 해당 점에서 움직일 수 있는 모든 방향을 queue에 추가한다. 이 때 막히거나 방문한 곳은 push하지 않는다.

 

더해서 맵과 같은 크기의 이중 배열 visited에 방문한 곳을 최단 기록을 넣어준다.(방문하지 않은 곳은 0)

 

시작 점은 (1,1)로 고정이다. queue에 (1,1)을 넣고 DFS를 실행하면 아래와 같은 결과가 나오고 도착 지점의 visited array의 값을 출력해준다.

 

위 그림 순서와 같이 시작하여 visited를 업데이트 시켜준다.

---

위 그림과 같이 완성 할 수 있다.

 

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


function solution(){
    let answer = Number.MAX_VALUE;
    let data = [];
    let [N,M] = input().split(' ').map((v)=>+v);
    let pos = [0,0];
    let count = 0;
    for(let i = 0; i < N; i++){
        data.push(input().split('').map((v)=>+v));
    }
    // console.table(data);

    const DFS = (pos,count) =>{
        if(pos[0]=== N - 1 && pos[1] === M -1){
            answer = answer > count + 1 ? count+1 : answer;
            return
        }
        // console.log(pos);
        // console.table(data);
        if(pos[0] < N - 1){
            if(data[pos[0]+1][pos[1]]===1){
                data[pos[0]][pos[1]] = 2;
                DFS([pos[0]+1,pos[1]],count + 1);
                data[pos[0]][pos[1]] = 1;
            }
        }
        if(pos[1] < M - 1){
            if(data[pos[0]][pos[1]+1]===1){
                data[pos[0]][pos[1]] = 2;
                DFS([pos[0],pos[1]+1],count + 1);
                data[pos[0]][pos[1]] = 1;
            }
        }
        if(pos[0] > 0){
            if(data[pos[0]-1][pos[1]]===1){
                data[pos[0]][pos[1]] = 2;
                DFS([pos[0]-1,pos[1]],count + 1);
                data[pos[0]][pos[1]] = 1;
            }
        }
        if(pos[1] > 0){
            if(data[pos[0]][pos[1]-1]===1){
                data[pos[0]][pos[1]] = 2;
                DFS([pos[0],pos[1]-1],count + 1);
                data[pos[0]][pos[1]] = 1;
            }
        }
    }

    DFS(pos,0);
    console.log(answer);
}

solution();