cheolung.dev

[JavaScript] 게임 맵 최단거리

Programmers
2024년 3월 25일
/thumbnail/programmers.png

💻 Code

function solution(maps) {
    // 1. 방향벡터 설정
	const dx = [-1, 0, 1, 0];
	const dy = [0, -1, 0, 1];
 
	// 2. 행렬 크기 정의 및 방문 행렬 생성
	const rows = maps.length;
	const cols = maps[0].length;
	const visited = maps.map((r) => r.map((c) => 1));
 
	// 3. 시작점 설정
	const queue = [[0 ,0]];
 
	// 4. bfs
	while(queue.length){
		const [x, y] = queue.shift();
		// 4-1. 현 위치에서 탐색
		for(let i=0; i<4; i++){
			const nx = dx[i] + x;
			const ny = dy[i] + y;
 
			// 4-2. 범위 내에 있는지 확인
			if(nx < rows && ny < cols && nx >= 0 && ny >= 0){
				// 4-3. 조건 확인 (막혀있거나, 방문했거나 등)
				if(maps[nx][ny] !== 0 && visited[nx][ny] === 1){
					// 4-4. 카운트 증가하고 큐에 넣기
					visited[nx][ny] = visited[x][y] + 1;
					queue.push([nx, ny])
				}
			}
		}
	}
	// console.log(visited);
	return visited[rows-1][cols-1] !== 1 ? visited[rows-1][cols-1] : -1;
}

해설

🤔 왜 이 문제에 BFS 알고리즘을 사용할까?

BFS는 최단 경로를 보장한다. => BFS는 너비 우선으로 탐색하기 때문에 출발 지점으로부터 가까운 곳부터 탐색을 진행한다. 이러한 특성 때문에 목적지에 도착했을 때, 해당 경로가 최단 경로임이 보장된다.

반면, DFS는 깊이 우선이기 때문에 최단경로를 보장하지 않을 뿐더러, 한 경로를 끝까지 탐색한 후 른 경로로 넘어가기 때문에 시간이 오래걸린다.

↔️ 방향벡터 사용하는 패턴

  1. 방향벡터 설정하기
  2. 방문 현황 행렬 만들기, 행과 열 크기 설정
  3. 시작점 설정 (큐 생성)
  4. bfs 시작 (큐와 while문)
    1. 현 위치에서 탐색
    2. 범위 내에 있는지, 제한되지는 않는지
    3. 조건에 맞다면 카운트 증가 및 큐에 삽입