[Python] 프로그래머스 Lv2_게임 맵 최단거리

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

프로그래머스

 

• ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임
• 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리
• maps: 게임 맵의 상태
• 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return
• 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않음
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있음

 

 

• 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시

• 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길
• 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동
• 게임 맵을 벗어난 길은 갈 수 없음

 

• 캐릭터가 상대 팀 진영으로 가는 두 가지 방법
• 1) 11개의 칸을 지나 상대 팀 진영에 도착

• 2) 15개 칸을 지나 상대 팀 진영에 도착 

• => 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 첫 번째 방법이 상대 팀 진영으로 가는 가장 빠른 방법

 

• 만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있음

 

 

"""
입출력 예시)

maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] -> 11
maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -> -1
"""

# maps = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] -> 11
# 주어진 maps의 예시

 

 

 

## 의사코드 ##

# 최단거리 -> BFS
# -> deque

# 캐릭터가 이동할 수 있는 범위
# dx = [-1, 1, 0, 0]
# dy = [0, 0, -1, 1]
#   -> for i in range(4):
#           nx = x+dx[i]
#           ny = y+dy[i]

# 상대방 진영: (n,m)
#    n = len(maps)
#    m = len(maps[0])

# 처음 캐릭터 위치: (1,1)

# 0은 벽이 있는 자리, 1은 벽이 없는 자리
# -> 캐릭터는 1에서만 이동 가능

# 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도
# -> 상대 팀 진영 위치인 (n,m) 바로 윗칸의 값이 0인 경우
# => (n-1, m) = 0

# return 
# 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값
# 상대 팀 진영에 도착할 수 없을 때는 -1

 

 

 

첫 번째 시도

 

from collections import deque
def solution(maps):
    n, m = len(maps), len(maps[0])
    # 캐릭터가 이동할 수 있는 범위
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque([1, 1])

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 이동할 수 있는 경우 탐색 진행
            if 0 <= nx <= n and 0 <= ny <= m: # nx, ny가 게임 맵을 벗어나지 않고
                if maps[nx][ny] == 1: # 위치의 값이 1인 경우
                    maps[nx][ny] = maps[x][y] + 1 # 상대 팀 진영에 도착하는 방법의 수 + 1
                    q.append([nx, ny])

    return maps[n][m] if maps[n][m] > 1 else -1

-> deque([1, 1])로 작성해서 TypeError: cannot unpack non-iterable int object 발생

 

 

 

통과한 코드

 

from collections import deque
def solution(maps):
    n, m = len(maps), len(maps[0])
    # 캐릭터가 이동할 수 있는 범위
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    q = deque([(0, 0)])

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 이동할 수 있는 경우 탐색 진행
            if 0 <= nx < n and 0 <= ny < m: # nx, ny가 게임 맵을 벗어나지 않고
                if maps[nx][ny] == 1: # 위치의 값이 1인 경우
                    maps[nx][ny] = maps[x][y] + 1 # 상대 팀 진영에 도착하는 방법의 수 + 1
                    q.append((nx, ny))

    return maps[n-1][m-1] if maps[n-1][m-1] > 1 else -1

-> deque([(0, 0)])로 작성 => 괄호 추가

 

• deque([(1, 1)]), return maps[n][m] if maps[n][m] > 1 else -1 로 하면
  • -> IndexError: list index out of range 발생

• q.append((nx, ny))
  • [(nx, ny)]로 하면 에러남

 

 

 

cf) 이전에 작성했던 코드

 

https://monzheld.tistory.com/57

 

[Python] 프로그래머스 Lv2_게임 맵 최단거리

 

 

 

참고)

 

https://programmers-story.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-deque-TypeError-cannot-unpack-non-iterable-int-object

파이썬 deque TypeError: cannot unpack non-iterable int object