격자형 구조에 관한 포스트를 참고하면 좋다.

게임 맵 최단거리

n x m 크기의 2차원 배열 maps가 매개변수로 주어진다. 처음 위치 (0,0)에서 (n, m)까지 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값 반환, 도착할 수 없을 때는 -1 반환.

제한사항

• 1<=n, m<=100인 자연수
• n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 없음.
• maps 내부의 값은 0, 1. (0은 갈 수 없고, 1은 갈 수 있음)

입력 예시

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]

출력 예시
11

얼음틀 문제

격자형 구조-문제 풀이(1)에서 풀었던 얼음틀 문제와 아주 유사하다.
얼음틀 문제는 탐색의 횟수(bfs로 해결했기에 bfs가 호출된 횟수)를 묻는다.

해당 문제

이 문제는 시작 위치와 목적지가 정해져 있고, 목적지에 도달하기까지 최단 거리로 거치는 노드의 개수를 묻는다.

---

문제 풀이

입출력 예시를 기준으로 다음과 같이 그림을 그려볼 수 있다.

문제가 되는 지점은 (2,2) 지점이다. (1,2)와 (2,3)으로 이동할 수 있다. 따라서 탐색 알고리즘을 2가지로 생각할 수 있는데, 깊이우선탐색의 경우 재귀를 활용하여 (1,2)에서 도착점까지 도달하는 연산과 (2,3)에서의 연산이 독립적으로 시행되게 된다. 너비우선탐색을 사용한다면 (1,2)과 (2,3)이 도착점까지 도달하는 과정이 같이 일어난다.

첫 번째 풀이 - DFS

첫 시도는 DFS를 활용하여 재귀함수로 구현해보았다. dfs를 이용한다면 (2,2)과 같은 지점에서 탐색 함수를 호출하게 된다. 이 예시에서는 총 2번 호출하여 2가지 거리값을 반환하게 될것이다.

그러나 효율성 테스트 전부에서 런타임 에러가 발생했다.

def solution(maps):
    dx = [-1, 0, 1, 0]  # 상, 좌, 하, 우
    dy = [0, -1, 0, 1]
    answer = []

    def dfs(x, y, path):
        path.append((x, y))
        
        if x == len(maps)-1 and y == len(maps[0])-1:
            answer.append(len(path))
            path.pop()
            return # 도착하면 함수 빠져나옴.
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<len(maps) and 0<=ny<len(maps[0]):
                if maps[nx][ny] == 1 and (nx, ny) not in path:
                    dfs(nx, ny, path)
        path.pop() 
        
    dfs(0, 0, [])
    
    return min(answer) if answer else -1

실패 원인 분석

dfs와 bfs의 가장 큰 차이는 dfs는 재귀 형태라는 것이다. 따라서 dfs로 코드를 짜는 경우 필요 이상으로 함수가 호출되고 있는지를 따져봐야 한다. 즉 최악의 경우 몇번까지 탐색이 이루어지는지 생각해야 한다.

비효율

다음 코드는 모든 경우를 탐색한 후 탐색한 전체 경우에서 최단거리로 이동한 경우를 찾아 반환한다. 위와 같은 예시에서는 2가지 경우밖에 나오지 않았기에 문제가 되지 않는다. 그러나 그래프의 크기가 훨씬 커지고 특정 위치에서 이동할 수 있는 경우가 늘어난다면 그 경우만큼의 제곱의 호출이 일어날 수밖에 없다.

방문의 여부를 확인하는 연산 (nx, ny) not in path 또한 리스트를 탐색하므로 $O(n)$의 시간복잡도를 갖는다.

다음과 같은 비효율을 해결하기 위해서는 최단거리를 찾은 즉시 그 경우를 반환해야 한다. 이를 위해서는 모든 경우를 탐색하게 되는 DFS가 아닌 BFS를 활용하여 조건에 맞는 경우 바로 반환하는 형태로 코드를 작성해야 한다.

두 번째 풀이 - BFS

먼저 도착한 경우 조기 종료되도록 한다. 위와 똑같이 (2,2)에서 2가지 경우로 분기된다. 탐색의 기준을 상, 좌, 하, 우 로 정했기에 (1,2) → (2,3) 순서로 큐에 들어가며 이때 너비우선탐색 알고리즘으로 각각 탐색 순서가 정해진다.

(1,2) → (2,3) → (0,2) → (2,4) → (0,3) → (3,4) → (0,4) → (4,4) 종료

queue를 사용하여 위와 같은 너비우선 탐색을 구현할 수 있다.

from collections import deque

def solution(maps):
    dx = [-1, 0, 1, 0]  # 상, 좌, 하, 우
    dy = [0, -1, 0, 1]
    n, m = len(maps), len(maps[0])
    
  	# 방문 여부를 확인하기 위한 T/F 리스트
    visited = [[False for j in i] for i in maps]
    dq = deque([(0,0)])   
    
  	# 특정 조건이 될 때까지 무한 반복
    while visited[n-1][m-1] == False:
        if not dq: 
            return -1 # 불가능한 경우 바로 종료
        x,y = dq.popleft()
        visited[x][y] = True
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<n and 0<=ny<m:
                if maps[nx][ny] == 1 and visited[nx][ny] == False:
                    # 이동 횟수를 쌓아감
  					maps[nx][ny] += maps[x][y]
                    dq.append((nx,ny)) 
                    
    return maps[n-1][m-1]

첫 번째 풀이와 공통점은 dxdy를 사용하여 탐색의 기준을 정하고 시작점에서부터 탐색이 가능한 경우 이동한다는 것이다.

차이점은 너비우선탐색을 사용하여 조건을 만족시키는 경우 곧바로 종료하도록 했다. 따라서 최소 거리가 가장 먼저 끝나므로 최소 거리를 반환할 수 있다.