프로그래머스 - 미로 탈출

문제 링크 ▶︎ 프로그래머스 미로 탈출

문제 전략

이 문제는 BFS 로 푼 문제이다.
처음에는 DFS로 풀려고 했지만 BFS가 효율이 더 좋다고 생각해 BFS로 풀었다.

구현은 start -> lever 까지의 최소 거리를 구하고, lever -> end 까지의 최소 거리를 구해서 두 값을 더했다.
만약 도달할 수 없다면, -1을 출력하고 두 값중에 -1이 있다면 -1을 출력하고 둘다 -1이 아니라면 두 값의 합을 출력한다.

코드

from collections import deque
def solution(maps):
    answer = 0
    rows = len(maps)
    cols = len(maps[0])
    start = []
    end = []
    lever = []
    maps = [list(s) for s in maps]
    
    dx = [1,0,-1,0]
    dy = [0,-1,0,1]
    
    def bfs(s,e):
        s_x, s_y = s[1], s[0]
        e_x, e_y = e[1], e[0]
        visit = [[0] * (cols) for _ in range(rows)]
        q = deque()
        q.append((s_y,s_x))
        answer = -1
        while q:
            y, x = q.popleft()
            if y == e_y and x == e_x:
                answer = visit[y][x]
                break
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                if 0 <= ny < rows and 0 <= nx < cols:
                    if maps[ny][nx] != 'X':
                        if visit[ny][nx] == 0:
                            visit[ny][nx] = visit[y][x]+1
                            q.append((ny,nx))
    
        return answer
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S':
                start += [i,j]
            if maps[i][j] == 'E':
                end += [i,j]
            if maps[i][j] == 'L':
                lever += [i,j]

    a = bfs(start,lever)
    b = bfs(lever,end)
    
    if a == -1 or b == -1:
        return -1
    else:
        return a + b

개선 사항

문제를 보고 DFS, BFS 중에 뭘로 풀지 고민을 충분히 해봐야함.