[프로그래머스] 미로탈출 (BFS) LV2

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

프로그래머스

📌 BFS로 푼 코드

from collections import deque

def bfs(maps, x, y, n,m, target, time):
    visited = [[False for _ in range(m)] for _ in range(n)]
    queue = deque([(x,y,time)])
    visited[x][y] = True
    direction = [(-1,0), (0,1), (1,0), (0,-1)]
    
    while queue:
        x, y, time = queue.popleft()
        #print(x, y, time)
        
        if maps[x][y] == target:
            return time #목표 지점까지 도달한 경우 거리 반환
        
        for dx, dy in direction:
            nx, ny = x + dx, y+dy
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X' and not visited[nx][ny]:
                queue.append((nx, ny, time + 1))
                visited[nx][ny] = True
    
    return -1 # 목표 지점까지 도달할 수 없는 경우 -1 반환
    
                
def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])

    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                sx, sy = i, j
            elif maps[i][j] == "L":
                lx, ly = i, j
    
    #S->L 까지 BFS
    L_time = bfs(maps, sx, sy, n, m, "L", 0)
    if L_time == -1: #출발지에서 L까지 도달하지 못하는 경우
        answer = -1
    else:
        #L->E 까지 BFS
        E_time = bfs(maps, lx, ly, n, m, "E", 0)
        if E_time == -1: #L에서 도착지까지 도달하지 못하는 경우
            answer = -1
        else:
            answer = L_time + E_time
            
    return answer

📌 DFS로 풀다가 망한 코드

① 깊은 복사 해줘야 함

② 시간 초과 나옴

import copy   
import sys
sys.setrecursionlimit(10**6)
#레버를 당겨야지만 도착지의 문이 열림
#레버까지 가는 DFS 먼저 구하고
#도착지까지 가는 DFS 구해서 더하기

def dfs(maps, i, j, m, n, pre_visited, target, t):
    global dis
    visited = copy.deepcopy(pre_visited)
    visited[i][j] = True
    direction = [[-1,0], [0,1], [1,0], [0,-1]]
    if target == maps[i][j]:
        print(t, dis)
        dis = min(t, dis)
    for d in direction:
        dx, dy = d[0], d[1]
        x, y = i+dx, j+dy
        if 0 <= x < n and 0 <= y < m and maps[x][y] != 'X' and not visited[x][y]:
            dfs(maps, x, y, m, n, visited, target, t+1)
    
def solution(maps):
    global dis
    dis = int(1e9)
    answer = 0
    n, m = len(maps), len(maps[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                sx, sy = i, j
            elif maps[i][j] == 'L':
                lx, ly = i, j
    
    dfs(maps, sx, sy, m, n, visited, "L", 0)
    if dis == int(1e9): #출발지에서 L까지 못가는 경우
        answer = -1
    else:
        print(dis)
        L_dis = dis
        dis = 1e9
        visited = [[False for _ in range(m)] for _ in range(n)]
        dfs(maps, lx, ly, m, n, visited, "E", 0)
        if dis == 1e9:
            answer = -1
        else:
            E_dis = dis
            answer = L_dis + E_dis
        
    return answer