[Programmers / Level2] 게임 맵 최단거리

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

프로그래머스

---

 

<내코드>

from collections import deque

dxs = [0, 1, -1, 0]
dys = [1, 0, 0, -1]

def is_valid(nx, ny, N, M, maps):
    return 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 1

def bfs(maps):
    N, M = len(maps), len(maps[0])
    queue = deque([(0, 0)])
    visited = [[-1 for _ in range(M)] for _ in range(N)]  # 거리(단계 수)를 저장
    visited[0][0] = 1  # 시작 위치의 거리를 1로 초기화
    
    while queue:
        x, y = queue.popleft()
        
        if x == N-1 and y == M-1:
            return visited[x][y]  # 목표 지점에 도달했을 때의 거리 반환
        
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny, N, M, maps) and visited[nx][ny] == -1:
                visited[nx][ny] = visited[x][y] + 1  # 이전 위치의 거리에 1을 더함
                queue.append((nx, ny))
    
    return -1  # 목표 지점에 도달할 수 없는 경우

def solution(maps):
    return bfs(maps)

 

나만의 BFS 푸는 로직 / 순서

• visited 테이블 정의하기 (False, 0, -1)등으로 값 초기화 시켜주기
• bfs내부로 들어가서 덱을 정의하고 처음 시작점을 방문한곳으로 체크해주기
  • 반복문 뺑뺑이 돌리기, 정의했던 증분값(좌, 우, 상, 하)을 더해서 is_valid 유효성 검증해주기
  • is_valid는 다음과 같은 유효성을 검증한다.
    1. 범위 내부에 있는가? - N, M의 범위 제한
    2. 이동할 수 있는 곳인가? - grid 값의 정보가 '1' 인지 체크
    3. 방문했던 곳인가? - visited 방문표시 여부체크
  • 유효성을 검증했다면, 방문표시를 해준다.
  • 다른곳도 방문할 수 있도록 큐에다가 유효한 좌표를 넣어준다.

 

마주했던 에러들

 

ValueError: too many values to unpack (expected 2) 오류 

• queue.popleft()로부터 반환된 값이 예상한 것과 다른 형태로 반환되었을 때 발생함. 문제의 원인은 deque에 바로 (0,0)을 초기화 시키는 기상천외한 일을 해버려서... deque에서 popleft() 를 할 때 값이 올바르게 나오지 않는 경우가 생겼다.

 

 

 

 

BFS 로직이 잘 잡혀있어야 하는데 가끔(사실 아주 잘) 잊어먹어버린다...

기억보다는 기록을 위해 이렇게 적어두었다.