미로탐색 2178번

문제 해결 접근 방법

링크

• 백준-미로탐색 2178

미로 탈출

문제 이해

• 이 문제 N x M 크기의 미로에서 (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸수를 구하는 문제이다.
• 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
• 이동은 상하좌우로만 가능하다.

문제 해결 방식

• 그래프 탐색 알고리즘 중 너비 우선 탐색(BFS, Breadth-First Search)을 사용하여 해결할 수 있다.
• BFS는 시작 지점에서 가까운 노드부터 차례대로 탐색하기 때문에, 최단 경로를 찾는데 적합하다.

의사코드

1. 입력을 받아 미로를 2차원 배열로 저장
2. BFS를 위한 큐 생성
3. 시작점 (0,0)을 큐에 넣고 방문 표시
4. 큐가 빌 때까지 다음을 반복:
   • 큐에서 현재 위치를 꺼냄
   • 현재 위치가 도착점이면 이동 횟수 반환
   • 상하좌우 네 방향에 대해:
     • 새 위치가 미로 범위 내이고, 이동 가능하며, 방문하지 않았다면:
       • 새 위치를 큐에 넣고 방문 표시
       • 새 위치의 이동 횟수를 현재 위치 + 1로 설정

Node.js 구현 예시

const BAEKJOONFILE = "/dev/stdin";
const VSCODEFILE = "./coding/example.txt";

const fs = require('fs');
const input = fs.readFileSync(VSCODEFILE).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const maze = input.slice(1).map(line => line.split('').map(Number));

function bfs() {
	const queue = [[0, 0, 1]];
	const visited = Array.from({length: N}, () => new Array(M).fill(false));
	visited[0][0] = true;

	const dx = [-1, 1, 0, 0];
	const dy = [0, 0, -1, 1];

	while (queue.length > 0) {
		const [x, y, count] = queue.shift();
		
		if (x === N - 1 && y === M - 1) {
			return count;
		}

		for (let i = 0; i < 4; i++) {
			const nx = x + dx[i];
			const ny = y + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] === 1 && !visited[nx][ny]) {
				queue.push([nx, ny, count + 1]);
				visited[nx][ny] = true;
			}
		}
	}
}

console.log(bfs());

부분 설명

입력 처리

const [N, M] = input[0].split(' ').map(Number); 
const maze = input.slice(1).map(line => line.split('').map(Number));

• 첫 줄에서 미로의 크기 N과 M을 받고, 나머지 줄에서 미로의 구조를 2차원 배열로 변환한다.

BFS 함수

function bfs() { 
	const queue = [[0, 0, 1]]; 
	const visited = Array.from({length: N}, () => new Array(M).fill(false)); 
	visited[0][0] = true;

• BFS 함수를 정의하고, 시작점 (0,0)과 이동 횟수 1을 큐에 넣는다. 방문 배열을 생성하고 시작점을 방문 처리한다.

방향 배열

const dx = [-1, 1, 0, 0]; 
const dy = [0, 0, -1, 1];

• 상하좌우 이동을 위한 방향 배열을 정의한다.

BFS 루프

while (queue.length > 0) { 
	const [x, y, count] = queue.shift(); 
	if (x === N - 1 && y === M - 1) { 
		return count; 
	}

• 큐가 빌 때까지 반복하며, 현재 위치가 도착점이면 이동 횟수를 반환한다.

주변 탐색

for (let i = 0; i < 4; i++) { 
	const nx = x + dx[i]; 
	const ny = y + dy[i]; 
	
	if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] === 1 && !visited[nx][ny]) { 
		queue.push([nx, ny, count + 1]); 
		visited[nx][ny] = true; 
	} 
}

• 현재 위치에서 상하좌우를 탐색하며, 미로 범위 내이고 이동 가능하며 방문하지 않은 칸이면 큐에 추가하고 방문 처리한다.

블로그 내 관련 문서

참고 자료

출처 :

• Ray 수학