[프로그래머스_Python] DFS/BFS - 게임 맵 최단거리 [Lv. 2]

황준성·2024년 11월 8일

DFS/BFS 프로그래머스

프로그래머스

목록 보기

12/14

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

문제 이해

BFS의 대표문제라고 할 수 있을 정도로 정석적인 문제이다. 보통 BFS가 최단거리를 구하는데 사용한다고 하는데 정말 이런 basic한 문제를 만났다.

이 문제는 2차원 배열에서 시뮬레이션 처럼 움직이기 때문에 방향벡터 dx, dy를 만들어주고, 방향벡터를 대입하면서 이동이 가능한 곳이면 queue에 넣어주는 방식으로 동작한다. BFS에 대한 개념이 부족해서 까먹거나 헷갈린다면, 이 문제를 다시 풀어보면서 복기해보는 것도 좋은 방법이라고 생각한다.

코드

# 프로그래머스_BFS/DFS_게임맵최단거리
from collections import deque
def solution(maps):
    # 방향벡터 구현 동-서-남-북 순
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    # 행과 열 길이
    n = len(maps)
    m = len(maps[0])
    
    # 방문 처리 확인할 리스트
    visited = [[False] * m for _ in range(n)]
    
    queue = deque([(0, 0, 1)]) # x, y, cnt
    # cnt가 1로 시작하는 이유는 첫번째 값도 카운트 하기 때문
    
    visited[0][0] = True
    
    while queue:
        
        x, y, cnt = queue.popleft()
        # 목표 지점일 경우에 cnt 반환
        if x == n-1 and y == m-1:
            return cnt
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append([nx, ny, cnt+1])
        
    
    return -1

BFS가 최단거리를 구하기 적합한 알고리즘인 이유

BFS 개념을 아직 배우는 중이라 그런지 왜 BFS를 쓰면 최단거리를 구할 수 있는지 이해가 되지 않았다.

예를 들면 "만약 이 그림에서 처음 나오는 갈림길에서 오른쪽으로 가지 않고 윗쪽으로 가면 최단거리가 아니지 않나?"라는 생각을 했다.

큐랑 코드의 흐름에 대해 잘 이해한다면 그렇지 않다.

결론적으로 방향벡터의 순서마다 다르긴 하겠지만, (2,3)(빨간 화살표)과 (3,4)(파란 화살표) 둘다 방문한 적 없고 벽이 없는 곳이기 때문에 각각 큐에 들어간다. 그리고 거기서 또 한칸지난 좌표도 큐에 들어간다. BFS의 개념대로 가까이 인접해 있는 칸부터 하나씩 큐에 넣고 큐에 넣은 좌표를 기준으로 갈 수 있는 칸인지 확인을 하는 것이다. 그러다가 종점(n,m)에 도달하면 그때의 cnt 값이 반환되는 것이다.

결국 둘 방향 다 큐에 들어가서 확인을 한다. 하지만 순차적으로 하기 때문에 더 가까운 오른쪽 방향이 종점에 더 빨리 도달을 하게 되고, 그 cnt값을 반환하는 것이다. 순차적으로 확인하기 때문에 가장 빠른 길이 처음으로 리턴이 되는 거고, 그게 바로 최단 거리인 것이다! :D

방향벡터를 이차원 리스트로 구현한 코드

# 프로그래머스_BFS/DFS_게임맵최단거리
from collections import deque
def solution(maps):
    # 방향벡터 구현 동-서-남-북 순
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # 행과 열 길이
    n = len(maps)
    m = len(maps[0])
    
    # 방문 처리 확인할 리스트
    visited = [[False] * m for _ in range(n)]
    
    queue = deque([(0, 0, 1)]) # x, y, cnt
    # cnt가 1로 시작하는 이유는 첫번째 값도 카운트 하기 때문
    
    visited[0][0] = True
    
    while queue:
        
        x, y, cnt = queue.popleft()
        # 목표 지점일 경우에 cnt 반환
        if x == n-1 and y == m-1:
            return cnt
        
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append([nx, ny, cnt+1])
        
    
    return -1

똑같은 코드긴 하지만 개인적으로 나는 방향벡터를 두개로 나누어 사용한 것이 좋다. 사실 파이썬과 C언어 밖에 안 써봐서 잘은 모르지만, 파이썬만 반복문의 범위를 리스트를 이용할 수 있는 것 같다. 언젠가 파이썬 말고 다른 언어를 써야될 수도 있기 때문에 다른 언어로도 구현이 되는 풀이로 구현을 하는 것을 머릿속에 각인하고 싶기 때문이다.