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

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

 

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

 

• 주어진 것
  • 게임 맵의 모양이 maps 이차원 리스트로 주어진다
  • 이때 maps의 모양은 n*m의 형태이며 n과 m은 같을 수도 다를 수도 있다
  • mpas는 정사각형일수도 직사각형의 형태를 가질 수도 있다
  • maps에서 벽은 0이고 길은 1이다
  • 시작점은 항상 0,0 이다

maps의 예시

위의 표를 리스트로 표현 - maps

 

문제에서 구하라는 것은 목적지까지의 최단거리이며 목적지는 맵의 끝에 존재한다.

 

문제 풀이

 

1. 맵의 입력
2. 출발지를 deque에 넣어주기
3. 4방위 탐색을 위한 dx, dy 선언
4. while 반복문 실행, 이때 deque의 값이 존재할 때까지
5. 만약 다음 탐색의 범위가 맵의 안이라면 해당 탐색 범위의 숫자가 1인지 확인
6. 1이 맞다면 해당 범위를 deque에 넣어주고 이전 해당 지역의 숫자는 이전 칸  + 1로 변경
7. 탐색 종료 후 맵의 끝점 값에 따라서 값 반환

from collections import deque # deque 선언

def solution(maps):
    dx ,dy =  [-1,1,0,0],[0,0,-1,1] #거리 이동을 위한 이동 좌표 설정
    row = len(maps) # 맵의 크기를 알기위한 변수 설정 1 - 행, 가로
    col = len(maps[0]) # 맵의 크기를 알기위한 변수 설정 2 - 열, 세로
    q =  deque() # 자료구조 선언
    q.append((0,0))
    while q:  # 해당 while의 경우 q가 빌 때까지
        x,y = q.popleft() # 들어온 순서대로 가져오기
        for i in range(4): # 4방위 탐색
            nx = x + dx[i]
            ny = y + dy[i] 
            if 0<= nx < row and 0<= ny < col: # 주어진 맵을 벗어나는지 확인
                if maps[nx][ny]==1: # 탐색된 지역이 아닌 경우
                    maps[nx][ny] = maps[x][y] +1 # 이전 블럭에서 값 +1 해주기
                    q.append((nx,ny)) # 해당 nx,ny를 deque에 넣어주기
    if maps[row-1][col-1] != 1: # 만약 1이 아니라면 해당 경우는 가로막히지 않은 경우
        return maps[row-1][col-1] # 값 리턴
    else:
        return -1 # 가로막혀서 접근 불가인 경우 -1 리턴