[프로그래머스/Lv2] 게임 맵 최단거리

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

프로그래머스

 

 

코드

from collections import deque

def solution(maps):
    if len(maps) == 1 and len(maps[0]) == 1:
        return 1
    row_len = len(maps)
    col_len = len(maps[0])
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    def bfs():
        queue = deque()
        queue.append((0, 0))

        while queue:
            row, col = queue.popleft()
            if (row, col) == (row_len-1, col_len-1):
                return maps[row][col]

            for (y, x) in zip(dy, dx):
                new_row = row + y
                new_col = col + x
                if new_row < 0 or new_row >= row_len or new_col < 0 or new_col >= col_len or\
                    maps[new_row][new_col] == 0 or (maps[new_row][new_col] != 1 and maps[new_row][new_col] <= maps[row][col] + 1):
                    continue
                maps[new_row][new_col] = maps[row][col] + 1
                queue.append((new_row, new_col))
        return -1
    
    
    return bfs()

 

 

설명

이 문제는 손을 대질 못하겠어서 다른 사람의 풀이 코드를 그대로 들고왔다.

 

BFS를 사용해서 문제를 풀었고, DFS로 이 문제를 풀면 효율성 테스트에서 탈락하게 된다(DFS는 모든 루트를 탐색해야 하기 때문).

 

if len(maps) == 1 and len(maps[0]) == 1:
    return 1

맵의 크기가 1x1이라면 그대로 1을 반환한다.

 

row_len = len(maps)
col_len = len(maps[0])
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

row_len는 maps의 행 길이, col_len는 maps의 열 길이이다.

dx, dy는 동, 서, 남, 북으로 이동할 때 변화값을 기록한 리스트이다.

 

 

from collections import deque

def bfs():
    queue = deque()
    queue.append((0, 0))

    while queue:
        row, col = queue.popleft()
        if (row, col) == (row_len-1, col_len-1):
            return maps[row][col]

        for (y, x) in zip(dy, dx):
            new_row = row + y
            new_col = col + x
            if new_row < 0 or new_row >= row_len or new_col < 0 or new_col >= col_len or\
                maps[new_row][new_col] == 0 or (maps[new_row][new_col] != 1 and maps[new_row][new_col] <= maps[row][col] + 1):
                continue
            maps[new_row][new_col] = maps[row][col] + 1
            queue.append((new_row, new_col))
    return -1

BFS를 구현한 함수이다.

 

queue = deque()
queue.append((0, 0))

deque를 만들어 queue에 저장한다.

queue에 시작점 (0, 0)을 넣는다.

 

while queue:
    row, col = queue.popleft()
    if (row, col) == (row_len-1, col_len-1):
        return maps[row][col]

queue가 빌 때까지 반복한다.

row와 col 변수에 각각 queue에서 popleft한 값을 저장한다.

만약 여기서 (row, col)(계산할 현재 좌표)이 (row_len-1, col_len-1) 좌표(상대팀 진영 좌표)와 같다면 maps[row][col] 값을 반환한다.

 

for (y, x) in zip(dy, dx):
    new_row = row + y
    new_col = col + x
    if new_row < 0 or new_row >= row_len or new_col < 0 or new_col >= col_len or\
        maps[new_row][new_col] == 0 or (maps[new_row][new_col] != 1 and maps[new_row][new_col] <= maps[row][col] + 1):
        continue
    maps[new_row][new_col] = maps[row][col] + 1
    queue.append((new_row, new_col))

dy와 dx의 각 원소를 묶어서 (y, x) 튜플로 만들어 반복한다.

new_row 변수에 y를 row에 더한 값을 저장하고,

new_col 변수에 x를 col에 더한 값을 저장한다. 이 과정은 게임 캐릭터가 동, 서, 남, 북으로 이동하는 과정이다.

 

만약 이 때 새로운 좌표가

1. 좌표계를 벗어남

2. 길이 아님

3. 이미 지나간 길이면서 비용이 더 큼(더 먼 길)

위 세가지 조건에 포함된다면 아무런 동작을 하지않고 넘어간다.

 

조건에 포함되지 않는 좌표라면

새로운 좌표의 값에 현재 좌표의 값에서 1을 더한 값을 저장한다(거리 계산용).

queue에 새로운 좌표를 기록한다.

 

return -1

while 반복문이 끝나도 아무런 반환값이 없는 경우(상대팀 진영에 가지 못함)

-1을 반환한다.

 

 

return bfs()

bfs함수를 호출하여 반환되는 값을 반환한다.

---

참고: https://velog.io/@taekkim/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B2%8C%EC%9E%84-%EB%A7%B5-%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC

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

 

BFS 참고: https://doing7.tistory.com/72

[알고리즘] BFS with Python