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

 

 

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

 

 

첫 번째 풀이 : 실패

 

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    queue = deque()
    
    queue.append((0, 0, 0))
    
    while queue:
        #들어가 있는 성분을 뺀다.
        #x, y, 이전 위치까지 거리
        #현재 위치의 거리를 계산
        #사방 중에 방문하지 않았으면서 벽이 아닌 장소를 queue에 넣음.
        current = queue.popleft()
        x = current[0]
        y = current[1]
        dis = -current[2]

        if maps[x][y] == 1 or -maps[x][y] > dis + 1:
            maps[x][y] = -(dis + 1)
        
        #x+1, y
        if x+1 < m and maps[x+1][y] > 0:
            queue.append((x+1, y, maps[x][y]))
        #x-1, y
        if x-1 >= 0 and maps[x-1][y] > 0:
            queue.append((x-1, y, maps[x][y]))
        #x, y+1
        if y+1 < n and maps[x][y+1] > 0:
            queue.append((x, y+1, maps[x][y]))
        #x, y-1
        if y-1 >= 0 and maps[x][y-1] > 0:
            queue.append((x, y-1, maps[x][y]))
        
    return -maps[-1][-1] if maps[-1][-1] != 1 else -1

 

BFS를 구현하기 위해서 deque 라이브러리를 사용한다.

 

1. queue에서 꺼낸 성분에는 내가 현재 있는 위치, 이전 위치까지의 거리가 적혀있다.

2. 현재 칸의 위치를 이전 위치의 거리 +1로 업데이트하는데 맵을 표시하는 0, 1과 혼동하지 않기 위해 음수로 업데이트한다.

3. 그 후 현재 칸 기준 상하좌우의 칸 중 방문하지 않았으면서 벽이 아닌 칸을 queue에 넣는다.

4. 이를 반복

5. 다 돌아본 뒤에 maps의 상대방 진영의 성분값을 -1을 곱해 양수로 만들어 return하는데

     만약 전부 살펴본 뒤에도 상대 진영의 칸 값이 1이라면 도착하지 못한 것이므로 -1을 return한다.

 

 

두 번째 풀이 : 효율성 테스트 실패

 

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    queue = deque()
    
    queue.append((0, 0, 0))
    
    while queue:
        current = queue.popleft()
        x = current[0]
        y = current[1]
        dis = -current[2]
        
        if maps[x][y] == 1 or -maps[x][y] > dis + 1:
            maps[x][y] = -(dis + 1)
            
        if x == n-1 and y == m-1:
            break
        
        #x+1, y
        if x+1 < n and maps[x+1][y] > 0:
            queue.append((x+1, y, maps[x][y]))
        #x, y+1
        if y+1 < m and maps[x][y+1] > 0:
            queue.append((x, y+1, maps[x][y]))
        #x-1, y
        if x-1 >= 0 and maps[x-1][y] > 0:
            queue.append((x-1, y, maps[x][y]))
        #x, y-1
        if y-1 >= 0 and maps[x][y-1] > 0:
            queue.append((x, y-1, maps[x][y]))
        
    return -maps[-1][-1] if maps[-1][-1] != 1 else -1

 

 

먼저 BFS이므로 탐색하는 노드가 상대방의 진영이라면 첫 탐색 시가 가장 적은 칸수이다.

위 그림에서 깃발을 도착지라고 한다면, 3칸 째에 도착했다면 4칸 째를 살펴보지 않아도 3칸이 가장 짧은 거리가 된다.

그래서 현재 위치까지의 거리를 업데이트 한 후에

현재 x, y 정보를 토대로 상대방 진영의 칸이라면 break해서 나오도록 최적화 해주었다.

그리고 (0,0)에서 우하측 방향으로 진행하므로 queue에 넣는 순서를 (x+1, y), (x, y+1)이 먼저 들어가도록 순서를 변경하였다.

 

가장 중요하게도, 내가 항상 행렬의 행, 열과 직사각형의 가로, 세로를 매칭하는 것이 항상 헷갈리는데

이를 바꾸니까 정확도 테스트는 다 통과했다. 여기서 착각한 듯.

 

그런데 이렇게 하자 정확도 테스트는 모두 통과했지만, 효율성 테스트는 여전히 통과가 안되었다.

 

 

세 번째 풀이

 

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    
    queue = deque()
    
    queue.append((0, 0))
    
    while queue:
        x, y = queue.popleft()
            
        if x == n-1 and y == m-1:
            return maps[x][y]
        
        #x+1, y
        if x+1 < n and maps[x+1][y] == 1:
            maps[x+1][y] = maps[x][y] + 1
            queue.append((x+1, y))
        #x, y+1
        if y+1 < m and maps[x][y+1] == 1:
            maps[x][y + 1] = maps[x][y] + 1
            queue.append((x, y+1))
        #x-1, y
        if x-1 >= 0 and maps[x-1][y] == 1:
            maps[x-1][y] = maps[x][y] + 1
            queue.append((x-1, y))
        #x, y-1
        if y-1 >= 0 and maps[x][y-1] == 1:
            maps[x][y-1] = maps[x][y] + 1
            queue.append((x, y-1))
    
    return -1

 

개선점1. 음수가 아니라 양수로 표기

 

처음 생각에 map이 0과 1로 구성되어있기 때문에 방문표시를 하기 위해 양수를 사용한다면

(0,0)을 방문하는 지점에서 무한루프가 걸릴 것이라고 생각해 음수로 처리하였다.

 

살펴보니, (0,0)을 2번 방문하긴 하지만 두 번째 방문 시점에는

(0,0)에서 방문할 수 있는 칸의 값이 2가 되어 queue에 들어가지 못해 낭비라곤해도 크게 고려할 필요가 없었다.

 

개선점2. Queue내의 중복 제거

 

효율성 테스트 통과를 위해서는 Queue내에서 동일한 칸이 없도록 중복을 제거하여야 한다.

처음 코드의 경우 Queue에 일단 넣고, 그 후 Queue에서 꺼낸 후에 방문 체크를 했기 때문에

만약 Queue안에 있지만 꺼내지지 않아 방문체크가 안 된 경우, 중복으로 들어가는 낭비가 발생한다.

 

이를 해결하기 위해 이전 칸에서 다음 칸을 Queue에 넣을 때 값을 갱신(방문체크)해주는걸로 변경하였고,

Queue에 들어가는 순간 방문한 것으로 기록되기 때문에 Queue에 중복해서 들어가지 않게 되었다.

또, 이전 칸까지의 거리 값이 필요가 없어져 dis 변수가 제거되었다.

---

 

시간 복잡도

 

이거 언제 계산해볼까ㅎ

 

 

다른 사람의 풀이를 보면서 알게 된 점

 

DFS가 왜 안될까?

 

사실 처음 문제 형태를 봤을 때 DFS 문제 아닐까? 라고 생각을 했었다.

무울...로온....DFS로도 풀 수는 있는데 시간이 매우 오래 걸리게 된다.

즉, 효율성 테스트를 통과할 수 없다.

 

왜 그런지 살펴보기 위해 두 번째 풀이의 사진을 가져오면

 

 

 

BFS로 탐색하면 트리에서 단계(너비) 별로 탐색하기 때문에 

상대방의 진영에 가장 먼저 도착한 노드의 횟수가 자연스럽게 최수 횟수가 된다. 

이에 따라 4번째 혹은 그 밑의 단계를 볼 필요가 없다.

 

 

 

그러나 DFS로 탐색하게 된다면 위와 같은 순서로 탐색하게 되는데

2번을 탐색한 순간에도 4칸이 최소 횟수라는 확신을 가질 수 없다.

그렇기에 모든 탐색이 끝난 다음에 7번이 최소 횟수임을 알게 되고, 시간은 자연스럽게 길어지게 된다.

노드가 적으면 통과할 수 있지만 노드가 많다면 BFS에 비해서 기하급수적으로 증가하게 될 것이다.

 

 

상하좌우 방문 방법

 

x, y = queue.popleft()

#x+1, y
if x+1 < n and maps[x+1][y] == 1:
    maps[x+1][y] = maps[x][y] + 1
    queue.append((x+1, y))
#x, y+1
if y+1 < m and maps[x][y+1] == 1:
    maps[x][y + 1] = maps[x][y] + 1
    queue.append((x, y+1))
#x-1, y
if x-1 >= 0 and maps[x-1][y] == 1:
    maps[x-1][y] = maps[x][y] + 1
    queue.append((x-1, y))
#x, y-1
if y-1 >= 0 and maps[x][y-1] == 1:
    maps[x][y-1] = maps[x][y] + 1
    queue.append((x, y-1))

 

나 같은 경우는 if문 4개를 사용하여 위와 같이 풀었는데,

for문을 사용하여 아래와 같이 코드를 줄일 수 있다.

 

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

x, y = queue.popleft()

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
        maps[nx][ny] = maps[x][y] + 1
        queue.append((nx, ny))

 

 

행과 열, 가로와 세로

 

이번에도 역시 틀린 부분인데 한번 짚고 넘어가자면,

 

x는 가로축, y는 세로축이라고 생각해서 생기는 문제인데,

안 헷갈리려면 다음부턴 array[y][x]로 선언하는 것이 편할 것 같다.

 

 

고찰

 

BFS vs DFS

 

BFS	DFS
Queue	Recursion / Stack
최단 거리를 찾아야할 경우	검색 대상 트리가 방대할 경우