[프로그래머스] 게임 맵 최단거리

게임 맵 최단 거리 
Lv.2
https://school.programmers.co.kr/learn/courses/30/lessons/1844

 

 

작성 코드 (실패)

 

def solution(maps):
    answer = 0
    solutions = []

    def dfs(map, i, j, depth):    
        if i < 0 or j >= 5 or j < 0 or i >= 5 or map[i][j] == 0:
            return
        if (i == 4) and (j == 4) and map[i][j] == 1:
            return solutions.append(depth)
            
        maps[i][j] = 0
        
        // 상하좌우 탐색
        dfs(map, i + 1, j, depth + 1)
        dfs(map, i - 1, j, depth + 1)
        dfs(map, i, j + 1, depth + 1)
        dfs(map, i, j - 1, depth + 1)
    
    dfs(maps, 0, 0, 0)

    return solutions

 

• 입출력 예제1에 대해 14를 출력함

 

 

참고 코드

 

from collections import deque


def solution(maps):
    q = deque()
    // 무조건 첫 시작은 [0][0]
    q.append((0, 0))
    
    // 상하좌우 탐색 준비
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    // BFS
    while q:
        x, y = q.popleft()
        
        // 상하좌우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            // list index 내에 있으면서 방문하지 않았을 경우에만 탐색
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]) and maps[nx][ny] == 1:
                q.append((nx, ny))
                // 이전까지 걸린 거리 + 1 만큼!
                maps[nx][ny] = maps[x][y] + 1
                
    // 마지막 행 마지막 열의 값이 1이라면 목적지까지 도착하지 않은 것임 -> return -1
    if maps[len(maps) - 1][len(maps[0]) - 1] == 1:
        return -1
    else:
        return maps[len(maps) - 1][len(maps[0]) - 1]

 

• 상하좌우를 탐색하는데 참고할 만한 코드 ! 매우 신기한 코드
• 최단 ~~ 이면 dfs 보단 bfs 가 적합한 듯

• 해당 원소까지 가장 최단 거리가 저장됨 (방문하지 않았을 경우에만 탐색하므로)