Programmers / 게임 맵 최단거리 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 게임 맵 최단거리 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

from collections import deque

# bfs
def bfs(graph, visit):
    n = len(graph)
    m = len(graph[0])

    q = deque()
    visit[0][0] = True
    q.append((0, 0))

    ix = [1, -1, 0, 0]
    iy = [0, 0, 1, -1]

    while q:
        y, x = q.popleft()
        for i in range(4):
            nx = x + ix[i]
            ny = y + iy[i]
            if (0 <= nx < m and 0 <= ny < n and graph[ny][nx] == 1):
                if not visit[ny][nx]:
                    visit[ny][nx] = True
                    q.append((ny, nx))
                    graph[ny][nx] = graph[y][x]+1

    if graph[n-1][m-1] == 1:
        return -1
    else:
        return graph[n-1][m-1]


def solution(maps):
    answer = 0

    visit = [[False] * len(maps[0]) for _ in range(len(maps))]

    answer = bfs(maps, visit)

    return answer

---

※ 알아야 할 것

 

언어가 달라져도 BFS구현하는 것은 크게 다르지 않다.

DFS/BFS 등 그래프를 이용하여 푸는 문제들은 주어진 문제를 그래프로 잘 나타낼 수 있으면 쉽게 풀 수 있다.