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

📌 문제

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

📌 풀이

풀이 1 - (실패)

1. 미로를 2차원 배열로 표현하고, 시작 지점(S), 출구(E), 레버(L)의 위치를 찾는다.
2. BFS (너비 우선 탐색) 알고리즘을 사용하여 시작 지점(S)에서 레버(L)까지의 최단 거리를 계산한다.
3. BFS (너비 우선 탐색) 알고리즘을 사용하여 시작 지점(L)에서 레버(E)까지의 최단 거리를 계산한다.
4. 두 단계에서 계산한 거리를 합산하여 출발 지점(S)에서 출구(E)까지 이동하는 최단 거리를 구한다.
   5.만약 어떤 단계에서도 출구(E)에 도달할 수 없는 경우에는 -1을 반환합니다.

from collections import deque

def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])
    
    graph = [list(maps[i]) for i in range(n)]
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'S':
                start_y, start_x = i, j 
            elif graph[i][j] == 'E':
                end_y, end_x = i, j 
            elif graph[i][j] == 'L':
                lever_y, lever_x = i, j 
            

    dy= [1,0,-1,0]
    dx= [0,-1,0,1]
    def bfs(start_y, start_x, end_y, end_x):
        chk[start_y][start_x] = 0
        q= deque()
        q.append((start_y, start_x))

        while q:
            y,x = q.popleft()
            if y == end_y and x == end_x:
                return chk[y][x]
            
            for k in range(4):
                ny = y+ dy[k]
                nx = x+ dx[k]
                if 0<=ny<n and 0<=nx<m:
                    if graph[ny][nx] != 'X' and chk[ny][nx] =='inf':
                        chk[ny][nx] = chk[y][x] + 1
                        q.append((ny,nx))
        return None 
    
    
    chk = [['inf'] * m for _ in range(n)]
   # 출발지에서 lever까지 거리 구하기 
    distance1 = bfs(start_y, start_x, lever_y, lever_x)
    
   # lever에서 도착지까지 거리 구하기
    distance2 = bfs(lever_y, lever_x, end_y,end_x)
    
    if distance1 is None or distance2 is None:
        return -1
    else:
        return distance1+distance2

풀이 2 - (성공)

문제를 다시 읽어보니, 우선적으로 레버를 찍은다음, 레버에서 다시 도착지로 가야 한다. 이때 갔던곳을 또 갈 수 있다는 것이 기본 미로탈출 문제와는 다른점이다.

1. 출발지에서 레버까지의 거리 계산

• chk 배열 초기화
• chk 배열 업데이트

2. 레버에서 도착지까지의 거리 계산

• chk 배열 초기화
• chk 배열 업데이트

(중요!!!) 각 스텝을 시작할때 거리를 저장할 chk는 새롭게 시작해야 한다.

from collections import deque

def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])
    
    graph = [list(maps[i]) for i in range(n)]
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'S':
                start_y, start_x = i, j 
            elif graph[i][j] == 'E':
                end_y, end_x = i, j 
            elif graph[i][j] == 'L':
                lever_y, lever_x = i, j 
            

    dy= [1,0,-1,0]
    dx= [0,-1,0,1]
    def bfs(start_y, start_x, end_y, end_x):
        chk[start_y][start_x] = 0
        q= deque()
        q.append((start_y, start_x))

        while q:
            y,x = q.popleft()
            if y == end_y and x == end_x:
                return chk[y][x]
            
            for k in range(4):
                ny = y+ dy[k]
                nx = x+ dx[k]
                if 0<=ny<n and 0<=nx<m:
                    if graph[ny][nx] != 'X' and chk[ny][nx] =='inf':
                        chk[ny][nx] = chk[y][x] + 1
                        q.append((ny,nx))
        return None 
    
    
   
   # 출발지에서 lever까지 거리 구하기 
    chk = [['inf'] * m for _ in range(n)]
    distance1 = bfs(start_y, start_x, lever_y, lever_x)
    
   # lever에서 도착지까지 거리 구하기
    chk = [['inf'] * m for _ in range(n)]
    distance2 = bfs(lever_y, lever_x, end_y,end_x)
    
    if distance1 is None or distance2 is None:
        return -1
    else:
        return distance1+distance2