[프로그래머스] 게임 맵 최단거리 (BFS)

사용 언어: Python3

문제

게임 맵 최단거리

풀이

내 풀이

from collections import deque

def solution(maps):
    N = len(maps[0])
    M = len(maps)
    dist = [[0] * N for _ in range(M)]
    visited = [[0] * N for _ in range(M)]
    
    q = deque()
    q.append((N-1, M-1)) # 도착지점부터 출발
    visited[N-1][M-1] = 1
    dx, dy = [0,-1,0,1], [1,0,-1,0]
    while q:
        x, y = q.popleft()
        for w in range(4):
            xx, yy = x+dx[w], y+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=M:
                continue
            if maps[xx][yy] == 0 or visited[xx][yy]:
                continue
            q.append((xx, yy))
            visited[xx][yy] = 1
            dist[xx][yy] = dist[x][y] + 1
            
    ans = dist[0][0]
    return [-1, ans + 1][ans != 0]

• 효율성을 위해 도착지점부터 시작했지만 부분적으로 정답이다

내 풀이

from collections import deque

def solution(maps):
    N = len(maps) # ✅ N이 행 수 !!
    M = len(maps[0]) # ✅ M이 열 수 !!
    dist = [[0] * M for _ in range(N)]
    visited = [[0] * M for _ in range(N)]
    
    dx, dy = [0,-1,0,1], [1,0,-1,0]
    def BFS(x, y):
        q = deque()
        q.append((x, y))
        visited[x][y] = 1
        while q:
            x, y = q.popleft()
            for w in range(4):
                xx, yy = x+dx[w], y+dy[w]
                if xx<0 or xx>=N or yy<0 or yy>=M:
                    continue
                if maps[xx][yy] == 0 or visited[xx][yy]:
                    continue
                q.append((xx, yy))
                visited[xx][yy] = 1
                dist[xx][yy] = dist[x][y] + 1
    
    BFS(N-1, M-1)
    ans = dist[0][0]
    return [ans + 1, -1][ans == 0]

• 성공!
  • N과 M을 반대로 정해서 N과 M이 같은 테케를 제외하고는 모두 틀렸던 것이었다..ㅜ

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기