[프로그래머스] 미로 탈출 / BFS / Python 코드

BFS/DFS 문제 풀이를 익히기 위해 미로 탈출 문제를 풀었다. Lv.2에 이전에 백준에서 많이 풀어봤던 느낌이라 쉽게 접근하고 풀 수 있었다. 어제 풀었던 문제를 떠올리면서 힌트를 얻기도 했다.

 

 

문제 설명

문자열의 배열로 주어진 미로에서 레버를 찍고 출구까지 가는 최단 거리를 구하는 문제이다. 

상, 하, 좌, 우로 이동할 수 있으며 (대각선 불가)

output으로는 몇 칸을 이동했는지를, 탈출할 수 없으면 -1을 반환한다.

 

문제 해결

인접한 칸을 방문하면서 최단 거리를 구하는 문제라 BFS를 사용했다.

가장 먼저 구한 답이 최단 거리가 될 것이다.

DFS로 푼다면 모든 경우의 수를 다 구하기 때문에 비효율적임

 

일단 레버를 찍고 탈출구로 갈 수 있으므로 레버까지의 BFS 한 번, 출구까지의 BFS 한 번으로 목적지에 따라 두 번 나누어 풀었다.

목적지까지 가면서 방문하는 칸을 큐에 넣고 distance를 증가시켜 visited 역할도 한 번에 하도록 했다.

하나의 목적지에 도달하면 거기부터 다시 최단경로를 찾기 때문에 distance를 초기화해줬다.

 

주의 사항: 문제의 제한사항을 잘 읽어보자

"출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다."

 

 

풀이 코드

from collections import deque

def bfs(maps, start, target):    
    h = len(maps)
    w = len(maps[0])
    
    q = deque()
    q.append(start)
    
    dist = [[0 for i in range(w)] for j in range(h)]
    
    direction = [[0, -1], [1, 0], [-1, 0], [0, 1]]
    
    while (q):
        cur = q.popleft()
        y = cur[0]
        x = cur[1]

        for d in direction:
            if 0 <= x + d[1] < w and 0 <= y + d[0] < h:
                dx = x + d[1]
                dy = y + d[0]
                if dist[dy][dx] == 0:
                    if maps[dy][dx] == target:
                        dist[dy][dx] = dist[y][x] + 1
                        return [dy, dx], dist[dy][dx]
                    elif maps[dy][dx] != "X":
                        dist[dy][dx] = dist[y][x] + 1
                        q.append([dy, dx])
    return [], -1

def solution(maps):
    start = []
    for i in range(len(maps)):
        if "S" in maps[i]:
            start = [i, maps[i].find("S")]
    
    target = ["L", "E"]
    answer = 0
    for t in target:
        start, dist = bfs(maps, start, t)
        if dist == -1:
            return -1
        answer += dist
    
    return answer

먼저 start 좌표를 찾아서 탐색을 시작한다. 첫 번째 타겟인 레버를 만나면 레버의 좌표와 현재까지 거리를 반환한다. 레버의 좌표부터 다시 탐색을 시작해 출구를 만나면 모든 거리를 더해준다.

 

 

헤맸던 점

1. return 값의 형식을 통일하지 않아서

여러 오류를 마주했고 구글링 헛수고 하다가 문득 코드 오류 발견하고 해결했다. 그동안 많이 못 봤던 에러라서 정리를 해보겠다.

 

TypeError:  cannot unpack non-iterable int object

반복이 불가능한 int 객체를 unpack할 수 없다는 에러.

풀이 코드에서 return 값을 튜플로 설정해서 unpacking 하는 과정에서 발생한 것으로 추정. 

 

TypeError: 'int' object is not subscriptable

int형을 인덱싱 및 슬라이싱할 때 발생하는 에러.

이 에러 역시 풀이 코드에서는 좌표와 거리의 return 값을 리스트로 주고 있는데 답이 없을 때는 return 값을 -1로 설정해 solution 함수에서 인덱스로 접근했다가 마주한 에러였다.

 

너무 기초적이라서 쉽게 볼 수 없었던 이유가 있는 에러들이었다 ㅎㅎ.. 혹시 다시 만나게 된다면 바로 해결할 수 있겠다!

 

2. "O"인 칸만 큐에 넣어서

프로그래머스 질문하기에서 Jay EPH님의 글을 보고 아차 싶었다.

방문할 수 없는 노드를 제외하고는 방문할 수 있도록 해서 바로 해결했다.

밑의 예시를 보면 바로 이해가 된다!

# input
["SELXX", "XXXXX", "XXXXX", "XXXXX", "XXXXX"]

# output
-1

# correct
3

 

 

x, y 좌표가 스스로 헷갈리기도 하고 뜬금없는 오류에 시간을 좀 썼지만 난이도는 쉬웠던 문제였다. 풀이가 눈에 보이면 보이는대로 재밌고 너~무 모르겠으면 그런대로 다른 풀이 방법을 찾아 공부하는 재미가 있다. 방학이 3주 정도 남았고 며칠간 코딩을 할 수가 없어서 아쉽다.. 얼른 다른 재밌는 문제들도 풀고 싶다. 다음 주부터 다시 열심히 풀어야지!