프로그래머스 > 게임 맵 최단거리 (Python 3)

1. 문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임이다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리하다.

 

 

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길이다. 캐릭터는 동, 서, 남, 북으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없다.

 

 

첫번째 방법은 11칸을 지나서 도착이며, 두번째 방법은 15칸을 지나서 도착이다.

 

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

 

이때, 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 개수의 최솟값을 반환하여라.

 

 

 

2. 코드

(1) 1차 시도

dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌
minimum = 10001

def dfs(maps, now_r, now_c):
    global minimum
    n, m = len(maps), len(maps[0])

    if (now_r == n-1) and (now_c == m-1): # 적 진영에 도착한 경우
        if maps[now_r][now_c] < minimum:
            minimum = maps[now_r][now_c]
            return minimum

    for i in range(4):
        new_r = now_r + dr[i]
        new_c = now_c + dc[i]
        
        if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
            if maps[new_r][new_c] == 1:

                maps[new_r][new_c] = maps[now_r][now_c] + 1
                dfs(maps, new_r, new_c)
                maps[new_r][new_c] = 1
        
def solution(maps):
    global minimum
    now_r, now_c = 0, 0
    
    dfs(maps, now_r, now_c)
    
    if minimum == 10001:
        return -1
    
    return minimum

 

효율성 테스트를 통과하지 못했다.

 

 

(2) 2차 시도

from collections import deque

dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌

def bfs(maps, now_r, now_c):
    n, m = len(maps), len(maps[0])
    
    queue = deque()
    queue.append([now_r, now_c])
    
    while queue:
        r, c = queue.popleft()
        
        for i in range(4):
            new_r = r + dr[i]
            new_c = c + dc[i]

            if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
                if maps[new_r][new_c] == 0: 
                    continue

                if maps[new_r][new_c] == 1:
                    maps[new_r][new_c] = maps[r][c] + 1
                    queue.append([new_r, new_c])
                    
    return maps[n-1][m-1]
        
def solution(maps):
    r, c = 0, 0
    ans = bfs(maps, r, c)
    
    if ans == 1:
        return -1
    
    return ans

 

 

 

3. 설명

BFS로 문제를 풀면, 어떻게 하더라도 계속 시간 초과가 발생한다ㅠㅠ

그래서 아예 DFS로 바꿔서 풀었다.

 

- deque를 사용하여 현재 위치를 큐에 넣어두고, popleft()를 하여 현재 위치를 받아온다.

- 현재 위치 기준 상, 하, 좌, 우를 이동하면서 맵을 벗어나지 않고 1 값을 가지는 위치 모두를 큐에 저장한다. → 너비 우선 방식!

- 큐에 저장된 [행, 열] 좌표에 대해 maps 배열의 원소를 이전 좌표에 +1 한 값으로 바꿔주어, 해당 좌표까지 오는데 얼만큼의 비용이 들어가는지 저장한다.

 

- 만약 dfs()에서 반환한 값이 1인 경우는 적의 진영에 도달하지 못했다는 의미이므로 -1을 반환한다.

 

 

1. 최솟값을 갱신해줄 필요가 없다.

- DFS는 최단경로를 보장한다.

 

2. visited로 방문 여부를 판단할 필요가 없다.

- maps의 값이 1일 때만 방문하도록 하여 따로 방문 여부를 저장하는 배열이 필요하지 않다,