프로그래머스 Lv.2 게임 맵 최단거리

문제 링크

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

 

풀이

최단거리문제이므로 BFS를 이용한다.

 

기본값 설정

answer의 초기값은 0,

n, m은 각각 map의 x좌표의 영역의 크기, y좌표의 영역의 크기이다. 

move는 상하좌우 움직일 좌표를 모아둔 리스트이다.

    answer = 0
    n = len(maps)
    m = len(maps[0])
    move = [[-1,0],[1,0],[0,-1],[0,1]]

 

 

 

 

BFS 함수 만들기

BFS를 이용하기 위해 파이썬의 deque 기능을 이용한다.

from collections import deque

 

 

bfs함수에서는 현재 x좌표와 y좌표를 파라미터를 가진다.

    def bfs(x,y):

 

queue는 방문한 좌표를 저장하는 곳이다.

queue를 deque함수로 만든다.

queue에 현재의 (x,y)좌표를 넣는다.

        queue = deque()
        queue.append((x,y))

 

 

현재 좌표의 상하좌우의 칸을 확인한다.

현재 좌표는 queue의 가장 마지막 좌표이고

이 것을 pop하면서 현재 좌표의 정보를 저장한다.

if 그 상하좌우의 칸이 맵의 영역에 포함된다면

   if 그 상하좌우의 칸이 갈 수 있는 길이라면

      1) 그 상하좌우의 칸을 (현재 좌표의 값) + 1로 표시하면서

          맨 처음으로부터 몇번째 칸에 해당하는지 체크한다.

      2) 그 상하좌우의 칸을 방문한 좌표로 표시한다.

 

이것은 더이상 방문할 칸이 없을 때까지

(= queue의 원소의 수가 없을 때까지)

계속된다.

 

        while queue:
            x, y = queue.popleft()
            
            # 상하좌우 칸 확인하기
            for i in range(4):
                dx = x + move[i][0]
                dy = y + move[i][1]
                
                if 0 <= dx < n and 0 <= dy < m:
                    if maps[dx][dy] == 1:
                        maps[dx][dy] = maps[x][y] + 1
                        queue.append((dx,dy))

 

함수의 return값

상대팀 진영은 (n-1, m-1)에 위치한다.

따라서 maps[n-1][m-1]을 return한다.

        return maps[n-1][m-1]

 

결과값

맨 처음에는 (0,0)에 위치하므로

bfs함수의 파라미터에 (0,0)을 대입한다.

bfs(0,0)으로 상대방 진영까지 이동한 거리를 구할 수 있다.

단, 상대방 진영까지 이동할 수 없는 경우

maps[n-1][m-1]의 초기값인 1이 저장되어 있다.

이 때에는 -1을 return한다.

    answer = bfs(0,0)
    if answer == 1:
        return -1
    else:
        return answer

 

 

전체 코드

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    
    def bfs(x,y):
        queue = deque()
        queue.append((x,y))
        
        while queue:
            x, y = queue.popleft()
            
            # 상하좌우 칸 확인하기
            for i in range(4):
                dx = x + move[i][0]
                dy = y + move[i][1]
                
                if 0 <= dx < n and 0 <= dy < m:
                    if maps[dx][dy] == 1:
                        maps[dx][dy] = maps[x][y] + 1
                        queue.append((dx,dy))
        return maps[n-1][m-1]
    
    answer = bfs(0,0)
    if answer == 1:
        return -1
    else:
        return answer