[코딩테스트] 깊이/너비 우선 탐색(DFS/BFS) - 게임 맵 최단거리

---

문제

 

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

프로그래머스

 

 

최단거리 문제. 이 문제는 대표적인 BFS문제다. 캐릭터는 상하좌우 움직일 수 있으므로 이걸 중점적으로 생각해서 풀어야 한다.

 

 

 

---

전략

 

01. BFS

 일반적인 BFS로 풀되 각 노드에서 상하좌우로 움직일 때 움직인 노드가 범위를 벗어나거나, 벽인 경우, 그리고 되돌아가는 경우를 제외해야 한다.

 

 

---

풀이

 

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    
    dq = deque([(0, 0)])
    
    dx = (1, -1, 0, 0)
    dy = (0, 0, 1, -1)
    
    while dq:
        y, x = dq.popleft()
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < n and 0 <= nx < m:
                if maps[ny][nx] == 1:
                    maps[ny][nx] = maps[y][x] + 1
                    dq.append((ny, nx))
        
    return maps[-1][-1] if maps[-1][-1] > 1 else -1

 

 BFS로 풀기 위해 먼저 deque함수를 이용해 dq 큐를 하나 만들어주었다. 큐에는 (y, x)좌표가 들어간다. 그리고 상하좌우를 간단히 표현하기 위해 dx, dy 튜플을 각각 만들어서 현재 노드에서 x가 +-1 됐을 때, y가 +-1 됐을 때를 표현해주었다.

 

for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]

    if 0 <= ny < n and 0 <= nx < m:
        if maps[ny][nx] == 1:
            maps[ny][nx] = maps[y][x] + 1
            dq.append((ny, nx))

 

 큐에서 각 노드를 꺼내서 for문 range를 0, 1, 2, 3으로 설정해 상하좌우를 각각 체크할 수 있도록 하고 간단하게 표현하기 위해 ny, nx변수에 담았다. 이제 ny, nx는 각 노드에서 상하좌우의 값을 가리킨다. 이때, 이 값은 범위 안에 있어야 하므로 각각 0과 n, 0과 m 사이의 값이어야 하며 이 값이 0일 경우는 벽이므로 제외해야 한다. 따라서 maps[ny][nx] == 1일 경우에만 그 노드에 기존 값 +1을 해준다. 그리고 해당 노드를 dq 큐에 넣는다.

 

마지막으로 끝 좌표인 maps[-1][-1]를 출력해주는데 이 값이 1보다 크다면 그대로 출력해주고 1 이하라면 벽으로 막혀 도달할 수 없는 경우이므로 -1을 출력해준다.