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

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

프로그래머스

 

1. 내가 작성한 코드

from collections import deque

def solution(maps):
    
    bfs(maps,0,0)
    
    if maps[len(maps)-1][len(maps[0])-1] == 1:
        return -1
    else:
        return maps[len(maps)-1][len(maps[0])-1] - 1


def bfs(maps,x,y):
    queue = deque()
    queue.append([x,y])
    maps[x][y] = 2
    
    while queue:
        popV = queue.popleft()
        
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        
        x,y = popV
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>=len(maps) or ny>=len(maps[0]):
                continue
            if maps[nx][ny] == 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append([nx,ny])

 

2. 코드 해석 및 알게된 점

BFS를 이용하는 기본적인 문제이다 (이것이 취업을 위한 코딩테스트다에 나오는 미로찾기와 매우 흡사한 문제)

 

아래는 문제를 풀기 앞서, 개인적인 편의를 위해 변경해서 푼 부분이다.

• 문제의 조건은 start = (1,1) end = (n,m) 이었으나 편의를 위해 start = (0,0) end = (n-1,m-1)로 문제를 해결
• 매개변수 maps에서 벽은0, 길은1로 주어졌기 때문에 방문한 곳은 2부터 시작한다. (나중에 -1 해서 출력할 것)

from collections import deque

def solution(maps):
    
    bfs(maps,0,0)
    
    if maps[len(maps)-1][len(maps[0])-1] == 1:
        return -1
    else:
        return maps[len(maps)-1][len(maps[0])-1] - 1

 

1) BFS는 queue를 이용해야 하기 때문에 deque 라이브러리를 호출해준다.

 

2) start 지점인 0,0을 매개변수로 bfs 함수를 호출한다.

 

3) map[n-1][m-1]에 있는 값이 1 이면 return -1을 해준다. => 상대 팀 진영에 도착할 수 없는 경우

(len(maps) 는 n, len(maps[0])은 m) 

(방문한 곳은 2부터 시작하도록 설정했기 때문에 value가 1이라는 것은 방문을 한 번도 하지 않았음을 의미)

 

4) map[n-1][m-1]에 있는 값이 1이 아닌 경우 value에서 -1을 해서 return 해준다.

(첫 조건에서 방문한 곳은 2부터 시작하도록 임의로 설정했기 때문에 -1)

 

def bfs(maps,x,y):
    queue = deque()
    queue.append([x,y])
    maps[x][y] = 2

5) queue를 deque로 선언해주고, 첫 주소를 삽입한다. 또한 방문했음을 알리기 위해 첫 주소에 2를 대입해준다.

 

while queue:
        popV = queue.popleft()
        
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        
        x,y = popV

6) FIFO를 구현하기 위해 popleft()를 해주고, 이동할 좌표를 설정해준다.

 

(-1,0) => 상 (1,0) => 하 (0,-1) => 좌 (0,1) => 우 를 의미한다. 

 

사실 일반적인 상식으로는 x좌표는 좌우 y좌표는 상하를 의미하지 않나? 하고 고민을 했는데

 

2차원 행렬에서는 map[x=행,세로][y=열,가로]을 의미하기 때문에 x와 y의 역할이 바뀐다.

 

len(maps) 는 n(세로), len(maps[0])은 m(가로) 도 같은 이유이다.

 

(사실 이게 헷갈려서 처음에 틀렸음 ,, 😥)

 

7) 첫 위치인 x,y를 popV라는 변수에 넣어준다.

 

 for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>=len(maps) or ny>=len(maps[0]):
                continue
            if maps[nx][ny] == 0:
                continue
            if maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append([nx,ny])

 

8) 반복문을 이용해 상,하,좌,우를 한 칸씩 이동한 경우 구분해준다.

 

9) map의 영역을 벗어난 경우 continue를 해서 무시해주고

 

10) maps의 value가 0인 경우 (벽을 만났을 경우)도 continue해서 무시해준다.

 

11) maps가 이동할 수 있는 경우, maps[x][y] + 1 를 해준 후, 현 위치를 queue에 삽입해줌으로써 bfs가 돌아가게 만든다.

 

(maps[x][y] + 1을 해주는 이유는 이동할 때마다 그 전보다 1칸 더 이동했음을 알려주기 위해서)

 

 

3. 메모

• 2차원 행렬(arr[x][y])에서 x는 행(세로), y는 열(가로)을 가르키고 있음을 잊지말자