[프로그래머스 | 파이썬 / 자바스크립트] 게임 맵 최단거리(깊이/너비 우선 탐색(DFS/BFS)/level 2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

 

🐍파이썬

from collections import deque
def solution(maps):
    n = len(maps)   #행
    m = len(maps[0])    #열
    
    #이동할 좌표, 상하좌우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def bfs(x, y):
        queue = deque()
        queue.append((x, y))
        while queue:
            x, y = queue.popleft()
            for i in range(4):	#상하좌우를 확인하며 이동할 수 있는 좌표를 확인
                nx = x + dx[i]
                ny = y + dy[i]
                if nx >= n or ny >= m or nx < 0 or ny < 0:	#배열의 범위를 벗어난 경우
                    continue
                if maps[nx][ny] == 0:	#막다른 길
                    continue
                if maps[nx][ny] == 1:	#옳은 길을 찾은 경우
                    maps[nx][ny] = maps[x][y] + 1	#이전 칸의 값 + 1을 새로 발견한 칸에 대입해 이동횟수를 체크
                    queue.append((nx, ny))
                if nx == n-1 and ny == m-1:	#오른쪽 끝에 도달한 경우
                    return maps[nx][ny]	#이동횟수를 리턴
        return -1	#오른쪽 끝에 도달하지 못한 경우 -1 리턴
    return bfs(0, 0)	#왼쪽끝(0,0)부터 bfs 시작

 

 

다른 풀이 방법

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])	#x, y, depth

    while queue:
        x, y, d = queue.popleft()
        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:	#배열의 범위를 벗어나지 않는 경우
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:	#막다른 길이 아닌 경우
                    maps[ny][nx] = d + 1	#깊이추가
                    if nx == x_h - 1 and ny == y_h - 1:	#목표지점에 도착하면
                        return d + 1	#현재까지의 깊이 + 1을 리턴
                    queue.append((nx, ny, d + 1))
    return -1

 

 

🐥자바스크립트

function solution(maps) {   
    n = maps.length
    m = maps[0].length
    
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    
    function bfs(x, y){
        queue = [[x, y]]
        maps[x][y] = 1
        while (queue.length > 0){
            [x, y] = queue.shift()	//구조분해 할당
            for(let i = 0; i < 4; i++){
                let nx = x + dx[i]
                let ny = y + dy[i]
                if (nx >= n || ny >= m || nx < 0 || ny < 0){
                    continue;
                }
                if (maps[nx][ny] === 0){
                    continue
                }
                if (maps[nx][ny] === 1){
                    maps[nx][ny] = maps[x][y] + 1
                    queue.push([nx, ny])
                }
                if (nx === n-1 && ny === m-1){
                    return maps[nx][ny]
                }
            }
        }
        return -1
    }
    return bfs(0,0);
}

 

 

다른 풀이 방법

function solution(maps) {
    var yLen = maps.length - 1;
    var xLen = maps[0].length - 1;

    var queue = [[0, 0]];
    var visited = Array.from(new Array(maps.length), () => new Array(maps[0].length).fill(false));

    var result = 0;

    while (queue.length) {
        result++;	#이동횟수 체크
        var size = queue.length;
        for (var i = 0; i < size; i++) {	#큐에 든 원소의 갯수만큼 dfs 반복
            var point = queue.shift();
            var curY = point[0];
            var curX = point[1];

            if (visited[curY][curX]) continue;	#방문한 경로인 경우 건너뛰기
			#방문한 경로가 아닌 경우
            maps[curY][curX] = 0;	#1을 0으로 덮어씌우기
            visited[curY][curX] = true;	#방문처리

            if (curY === yLen && curX === xLen) return result;	#목표지점 도달시 result 리턴
            
            #상하좌우를 확인하며 이동
            if (curY < yLen && maps[curY + 1][curX] === 1) queue.push([curY + 1, curX])
            if (curX < xLen && maps[curY][curX + 1] === 1) queue.push([curY, curX + 1])
            if (curY > 0 && maps[curY - 1][curX] === 1) queue.push([curY - 1, curX])
            if (curX > 0 && maps[curY][curX - 1] === 1) queue.push([curY, curX - 1])
        }
    }
    return -1;
}