백준 - 2178 미로 탐색

Park Inhye·2024년 3월 29일

코테 연습

목록 보기

31/37

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄
- 세로 N, 가로 M
다음 N개의 줄
- 미로 데이터

제한 조건

2 ≤ N, M ≤ 100

예시

// NOTE: 입력
4 6
101111
101010
101011
111011


// NOTE: 출력
15

해결

문제의 핵심

좌표의 유효성 확인하기

전역변수

end point
미로 데이터
- 1: 지나가지 않은 자리
- 0: 벽 또는 지나간 자리
- 지나간 자리는 1 > 0 처리 (visited)
상하좌우 좌표

let _END_ROW, _END_COL, _maze = null;
const _DIR = [[1, 0], [-1, 0], [0, 1], [0, -1]];

dfs

queue
- item: [x, y, count]
반복문
- queue가 텅텅 빌 때까지 반복
- 상하좌우 좌표의 유효성 확인
  - 0 ≤ x ≤ n - 1
  - 0 ≤ y ≤ n - 1
  - 지도에서 1이어야 함
- 유효한 경우
  - visit 처리
  - 현재 좌표 queue에 push
    - x와 y가 end point에 다다른 경우
  - return count

const dfs = () => {
    let _queue = [[0, 0, 1]];
    
    while(_queue.length) {
        const [_curX, _curY, _count] = _queue.shift(); 
        
        // NOTE: 끝에 다다른 경우
        if (_curY == _END_ROW && _curX == _END_COL) return _count;
        
        // NOTE: dfs 탐색
        for (let [dx, dy] of _DIR) {
            const [_newX, _newY] = [_curX + dx, _curY + dy];
            
            // NOTE: 범위를 벗어난 경우
            if (_newX < 0 || _newX > _END_COL || _newY < 0 || _newY > _END_ROW) continue;
            
            // NOTE: 벽이거나 방문한 경우
            if (_maze[_newY][_newX] == 0) continue;
            else _maze[_newY][_newX] = 0
            
            _queue.push([_newX, _newY, _count + 1]);
        }
    }
}

solution

end point 설정
maze 설정
dfs 실행

전체 코드

let _END_ROW, _END_COL, _maze = null;
const _DIR = [[1, 0], [-1, 0], [0, 1], [0, -1]];

const dfs = () => {
    let _queue = [[0, 0, 1]];
    
    while(_queue.length) {
        const [_curX, _curY, _count] = _queue.shift(); 
        
        // NOTE: 끝에 다다른 경우
        if (_curY == _END_ROW && _curX == _END_COL) return _count;
        
        // NOTE: dfs 탐색
        for (let [dx, dy] of _DIR) {
            const [_newX, _newY] = [_curX + dx, _curY + dy];
            
            // NOTE: 범위를 벗어난 경우
            if (_newX < 0 || _newX > _END_COL || _newY < 0 || _newY > _END_ROW) continue;
            
            // NOTE: 벽이거나 방문한 경우
            if (_maze[_newY][_newX] == 0) continue;
            else _maze[_newY][_newX] = 0
            
            _queue.push([_newX, _newY, _count + 1]);
        }
    }
}

const solution = () => {
    const [_condition, ...maps] = require('fs')
        .readFileSync('dev/stdin')
        .toString()
        .trim()
        .split('\n');
    
    [_END_ROW, _END_COL] = _condition.split(' ').map(v => +v - 1);
    
    _maze = maps.map(v => v.split('').map(v => +v));
    _maze[0][0] = 0;
    
    console.log(dfs());
};

solution();