프로그래머스 Lv2. 게임 맵 최단거리 [Python] - 깊이/너비 우선 탐색(DFS/BFS)

문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/1844

---

문제 핵심

1. n * m 크기의 maps가 주어지고 maps에서 0은 벽을 1은 길을 나타낸다.

2. 목표지점은 maps의 우측 하단 끝 지점이며 시작지점은 (1,1) 이다.

3. 캐릭터는 상하좌우로 움직일 수 있으며, 벽으로 이동하는 것은 불가능하다.

4. 목표지점에 도달하기 위해 최소한의 움직임을 구하기

---

첫 번째 방법

최단거리를 구하는 문제이기에 BFS탐색법을 사용했지만 시간 초과가 발생하였다..ㅎㅎ

def solution(maps):
    w = len(maps) - 1 
    h = len(maps[0]) - 1 
    visit = [] 
    going = [[0,0,1]] 
    while going:
        now = going.pop(0) 
        x, y, count = now[0], now[1], now[2] 
        if x == w and y == h: 
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: 
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and [nx, ny] not in visit and maps[nx][ny] == 1:
            
                going.append([nx, ny, count + 1]) 
                visit.append([nx, ny]) 
    return -1

기본적인 BFS 문제는 풀이방법이 비슷하다.
1. BFS문제면 이동할 때 사방팔방 다 이동하고 그 값을 저장하는 변수 필요 => 큐 사용

2. 위로 이동하고 좌우 옆으로 이동했을 때 해당 좌우가 방문했는지 저장하는 변수 필요  => 좌, 우, 상, 하 이동

 

1. 목표지점을 계산하기 위한 maps의 세로 길이와 가로 길이를 w ,h 로 정의

2. visit라는 방문한 지점을 담을 리스트 정의

3. going은 방문해야할 지점을 담을 리스트

4. now 는 현재 지점이고 x, y, count 는 현재 x, y좌표 및 이동 거리

5. 만약 목표지점일 경우 이동 거리를 리턴

6. dx, dy 에는 (1, 0), (-1, 0), (0, 1), (0, -1) 상하좌우 이동의 값을 넣고

7. 경계 및 벽에 막히지 않고, 방문한 지점이 아닐 경우 방문할 지점에 추가하고 방문한 지점에 추가

8.  모든 경로를 탐색후에도 만족하지 않으면 -1 리턴

 

---

그래서 뭐가 문제인가.. 알아봤는데 나는 방문한 지점을 담은 리스트 visit를 리스트로 사용했고 이 경우에서 방문 여부를 확인하는 로직인 not in을 사용할 경우 시간복잡도가 크게 상승한다는 얘기.. 이를 해결하기 위해 visit를 set로 선언하여 통과하였다.

---

두 번째 방법

def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set() 
    going = [[0,0,1]]
    while going:
        now = going.pop(0)
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visit and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

set 자료형의 경우 내부 해시테이블을 이용하여 포함여부를 확인할 때 리스트보다 빠른 속도로 확인이 가능하여 시간을 줄여 해결할 수 있었다.

---

세 번째 방법

뭔가 내가  쓴건 깔끔하지 않다고 해야하나.. 그래서 다른 사람 코드를 봤더니

going 리스트도 deque를 사용하여 속도를 더욱 줄이는 방법이 있고 깔끔했다.

from collections import deque
def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set()
    going = deque([[0,0,1]]) 
    while going:
        now = going.popleft()
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visited and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

deque를 사용하면 기존의 pop(), append()의 시간복잡도가 O(N)에서 popleft()를 통한 시간복잡도 O(1)로 줄어들기 때문에 n이 커질 경우 더욱 빠르게 문제해결이 가능해진다.