[프로그래머스 lv2] 게임 맵 최단거리 (bfs/dfs/파이썬) 2/3 -/R

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

Try1 -DFS

우선 아래는 DFS로 해결한 문제다.
답은 맞게 나온다. 그러나

n = 0
m = 0
answer = 10001

def dfs(x, y, maps, Visit, value):
    global n
    global m
    global answer
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    Visit[x][y]=True
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<= nx < n and 0 <= ny < m and not Visit[nx][ny] and maps[nx][ny] == 1:
            dfs(nx, ny, maps, Visit, value+1)
            Visit[nx][ny] = False
        if nx == 0 and ny == 0:
            if answer > value: answer = value
            return answer
        
def solution(maps):
    global n
    n = len(maps)
    global m
    m = len(maps[0])
    global answer
    Visit = [[False for _ in range(m)] for _ in range(n)]
    dfs(n-1, m-1, maps, Visit, 1)
    if answer == 10001: return -1
    return answer+1

결과

DFS는 최단거리 측정에는 좋은 방법이 아니다. 답이 아니다 싶으면 다시 돌아가서 또 탐방하고 탐방하기 때문. 갈림길이 나올 때마다 선택지가 무궁무진하게 늘어난다. 그리고 이 알고리즘은 가능한 모든

따라서, 이건 BFS로 풀어야한다.

Try2- DFS

from collections import deque

n = 0
m = 0

def bfs(x, y, maps, Visit):
    q = deque()
    global n
    global m
    global answer
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    Visit[x][y]=True
    q.append([x, y])
    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx = cx+dx[i]
            ny = cy+dy[i]
            if 0<= nx < n and 0 <= ny < m and not Visit[nx][ny] and maps[nx][ny] != 0:
                q.append([nx, ny])
                maps[nx][ny] = min(maps[cx][cy]+1, maps[nx][ny])
            if nx == 0 and ny == 0:
                return maps[0][0]
    return -1
        
def solution(maps):
    global n
    n = len(maps)
    global m
    m = len(maps[0])
    global answer
    Visit = [[False for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 1: maps[i][j] = 10001
    maps[n-1][m-1] = 1
    answer = bfs(n-1, m-1, maps, Visit)
    return answer

굉장한 결과다.

정답코드

결국 페이지에 있는 다른 사람이 푼 정답 코드를 가져왔다.

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

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

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

보다시피 훨씬 빠르고 효율적으로 나오는게 보인다.
queue에 depth 개념을 추가해서 넣어준 선택이 나처럼 기존 값을 grid 안에 넣고 min value를 비교하는 방식보다 훨씬 합리적이다.

Tech:

1. 우선 갈림길이 나오면 visit을 다시 초기화해줬다. 그래야 다시 돌아와서 dfs를 수행하니까. 저걸 false로 설정해주지 않으면 한 번만 도착하고 만다. 그전엔 왜 이렇게 false로 설정하는지 몰랐는데 직접 짜다보니 이해가 가는군
2. 그런데 dfs는 정답은 맞아도 효율성에서 전부다 시간 초과를 해버린다.
3. bfs도 잘 못 짜면 그렇게 된다.
4. 다른 사람의 코드인데, visit(nx)(ny) =False 설정 없이 deepcopy를 이용해 visit을 쓴 파트가 눈에 띈다.

https://velog.io/@tsi0521/%EB%AF%B8%EB%A1%9C-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-DFS-%EC%99%80-BFS-%EB%B9%84%EA%B5%90