[프로그래머스/Python] Level 2_게임 맵 최단거리(DFS/BFS)

📌문제 유형

DFS/BFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

- BFS 이용하여 1 씩 더하면서 이동 

from collections import deque

def solution(maps):
    answer = 0
    q = deque()
    q.append([0,0])
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    while q:
        x,y = q.popleft()

        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:
                    maps[nx][ny] = maps[x][y] + 1
                    q.append([nx,ny])
    if maps[len(maps)-1][len(maps[0])-1] == 1:
        return -1
    else:
        return maps[len(maps)-1][len(maps[0])-1]

 

📌다른 사람의 문제풀이

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

"maps[ny][nx] > d + 1: " 이 부분은 경로가 여러가지일 때 먼저 지나간 경로보다 최단 경로가 나올 때 업데이트 해주기 위해 작성하신 것 같은데 방문 배열을 따로 사용하지 않으셔서 해당 경로가 이미 지나간 곳인지 아닌지 체크가 안 되어 작성하신 것 같습니다. 방문배열을 사용하면 경로를 지나갈 때 방문체크를 하기 때문에 해당 부분이 없어도 테케 통과할 겁니다.

 

📌리뷰

- 그래프 + 최소 or 최대 = BFS