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

문제

프로그래머스 코딩테스트 고득점 Kit - 깊이/너비 우선 탐색(DFS/BFS)

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

코드 구현

from collections import deque

# BFS로 풀이
def solution(maps):
    answer = 0

    # 상 하 좌 우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque()         # 큐 선언 (이동 가능한 위치의 좌표를 담을 큐)
    q.append((0, 0))

    while(q):   # 큐가 빌 때까지 반복
        x, y = q.popleft()      # 왼쪽에서부터 꺼내서 해당 위치에서 상하좌우 이동 가능한지 판단하기

        for i in range(4):
            nx = x + dx[i]      # (상하좌우 순서대로) 이동 후의 x좌표
            ny = y + dy[i]      # (상하좌우 순서대로) 이동 후의 y좌표

            if(nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0])):      # 맵 범위를 벗어나면 X
                continue
            if(maps[nx][ny] == 0 or (nx == 0 and ny == 0)):     # 벽이 있으면 X, 시작점으로 다시 이동 X
                continue
            if(maps[nx][ny] == 1):      # 이동 가능한 위치 + 아직 방문하지 않은 지점이라면
                maps[nx][ny] = maps[x][y] + 1       # 현재까지의 거리로 업데이트
                q.append((nx, ny))                  # 해당 위치는 이동 가능하므로 큐에 삽입

    # for i in range(len(maps)):
    #     print(maps[i])

    answer = maps[-1][-1]       # 최종 상대방 칸 위치에 있는 값이 정답인 최단거리값

    # 1이라면 도착하지 못했다는 뜻이므로 -1 반환
    if(answer == 1):
        return -1

    return answer

풀이

• DFS/BFS 개념을 위해서 아래의 강의를 우선 참고하였다.
  [이것이 코딩 테스트다 with Python] 20강 DFS & BFS 기초 문제 풀이

  • DFS → 스택을 사용하여 재귀로 호출하며 깊이우선탐색
  • BFS → 큐를 사용하여 너비우선탐색

• 우선 최단거리를 구하는 문제이므로 BFS를 사용하여 풀어줄 수 있다.

  • 🚨 가중치가 없는 최단 경로 : BFS
    DFS : 특정 칸에 처음 도달했을 때까지의 경로 길이가 다른 경로를 통해 도달한 길이보다 짧다는 보장못함
    BFS : 특정 칸에 처음 도달했을 때까지의 경로 길이가 항상 최적임을 보장
    

  • 💡 DFS는 스텍 터질 위험이 커서 BFS 사용하는게 일반적으로 유리하다.
    💡 최대 길이를 구하는 문제는 BFS 가 유리하다는 의견이 많이있다.

    → 참고한 글

• 상, 하, 좌, 우를 이동할 때의 x와 y 좌표값의 변화에 대한 값을 dx, dy에 저장해두고 deque를 선언하여 시작한다.

• 기본 원리 : 이동 가능한 곳이고 + 한번도 이동하지 않은 곳이라면 → deque에 해당 위치의 좌표를 삽입한다.

  • deque에서 좌표값을 하나씩 popleft() → 해당 위치의 상하좌우 이동 가능한지 판단 → 가능하면 이동 + 좌표값 deque에 삽입

• 따라서 큐에 들어있는 좌표에 대해서 해당 위치의 상 하 좌 우를 다 따져보고,

  • 이동이 가능하면 → 좌표값 큐에 삽입 → 이동하였을 때의 거리값으로 업데이트
    이동이 불가능하면 → 해당 방향으로는 이동을 할 수 없으니 넘어가기