프로그래머스 BFS/DFS 문제입니다.

문제

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

[나의 풀이]

def solution(maps):
    
    from collections import deque

    # answer = 0

    # x,y,이동
    queue = deque([[0,0,1]])

    # n X m 크기

    n = len(maps)
    m = len(maps[0])

    visited = [[False]*m for _ in range(n)]
    visited[0][0] = True

    # 상우하좌
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]

    answer_list = []

    while queue:

        x,y,answer = queue.popleft()

        for i in range(4):
            newX = x + dx[i]
            newY = y + dy[i]

            if newX >=0 and newX < n and newY >= 0 and newY < m:
                if maps[newX][newY] == 1:
                    if not visited[newX][newY]:
                        queue.append([newX,newY,answer+1])
                        visited[newX][newY] = True

        if x == n-1 and y == m-1:
            answer_list.append(answer)

    

    if len(answer_list) == 0:
        return -1

    return answer

자주 풀어왔던 BFS/DFS 활용 최단 루트 찾기 문제입니다. deque()의 popleft() 함수를 사용하여 BFS 구조로 해결하였습니다.🐻‍❄️🐻‍❄️🐻‍❄️

[다른 사람의 풀이]

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

비슷한 다른 풀이로서 visted 리스트를 만들지 않고 지나온 지점마다 +1해주어 다음 위치가 1이 아닌지역일 때 이동하는 방식이었습니다.🐷🐷🐷

감사합니다.