게임 맵 최단거리

날짜 : 2023. 09. 28

사용 언어 : python

 

문제

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

 

코드

from collections import deque
def solution(graph):
    n, m = len(graph), len(graph[0])
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1: graph[i][j] = 0
            else: graph[i][j] = 1
                
    answer = 0
    queue = deque()
    queue.append([0, 0])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    while queue:
        x, y = queue.popleft()
        if x == (n-1) and y == (m-1):
            return graph[x][y] + 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx in range(n) and ny in range(m):  # 범위 확인
                if (nx, ny) != (0, 0) and graph[nx][ny] == 0:  # 방문여부 체크
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append([nx, ny])
    return -1

 

 

풀이

- 일반적인 BFS로 풀이하는 문제였다.

- 따로 방문여부를 저장하는 리스트를 만들지 않고, 이동 가능한 칸은 0, 벽은 1로 하되, 이동한 거리를 저장하도록 움직일 때마다 해당 좌표에 가산하는 방식으로 큐를 돌렸다.

- 다만 문제의 조건에서 1이 이동 가능한 칸, 0이 벽으로 제시되었기 때문에 문제 처음에 1을 0으로, 0을 1로 변환하는 작업을 실시하였다.

 

 

알게된 점

- 

 

 

참고 사이트

-