greentea31's Note

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

풀이 과정

상하좌우로 이동 가능한 좌표계에서, 통과 가능한 공간과 통과 불가능한 벽이 주어질 때, 시작점 (1, 1)에서 도착점 (n, m)까지 경로의 최단 거리를 구하는 문제이다.

문제의 예시에서 보이듯이, 위처럼 지도가 주어지면 최단 경로의 길이는 11이 된다.

좌표간의 가중치가 존재하지 않으므로 그냥 BFS를 돌려서 최단거리를 구하면 된다.

파이썬에서 BFS를 구현 시, 이미 접근한 좌표를 discovered 배열에 넣는, 예를 들어 discovered = [] 상태에서 [1, 1] 방문시 discovered.append([1, 1])로 좌표를 넣어주고 BFS로 진행할 좌표를 찾을 때 not in discovered 조건으로 구현하는 경우가 있다. 그러나 이 문제에서는 효율성 테스트에서 시간 초과가 발생할 것이다. set이나 dictionary 자료형이 아니면 in이나 not in으로 자료형을 탐색하는 연산의 시간복잡도는 O(N)이 된다.

이 문제 같은 경우에는 이미 방문한 점을 map에서 2로 바꿔준다거나 하는 방법으로 해결이 가능하다. 별도의 discovered 리스트로 방문 점을 판별하고 싶다면 discovered = [[0 for _ in range(m)] for _ in range(n)] 과 같이 별도의 방문점을 판별하는 2차원 배열을 선언후 값을 바꿔주어야 방문 가능 판단 연산이 O(1)이 된다.

소스 코드

import collections

def solution(maps):
    def bfs(maps, n, m):
        Q = collections.deque()
        Q.append([0, 0, 1])
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        
        while Q:
            cur_y, cur_x, dist = Q.popleft()
            for i in range(4):
                ny = cur_y + dy[i]
                nx = cur_x + dx[i]
                ndist = dist + 1
                if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1:
                    Q.append([ny, nx, ndist])
                    maps[ny][nx] = 2
                    if ny == n-1 and nx == m-1:
                        return ndist
        
        return -1
                
            
    answer = bfs(maps, len(maps), len(maps[0]))
    return answer

# discovered = [] 와 in으로 방문 여부 판단하면 in이 O(N)이라서 시간초과가 발생한다.