[프로그래머스] Level2 미로 탈출(python)

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

프로그래머스

 

1. 문제 해결 방법

 

BFS나 DFS를 이용하는 문제 

 

레버와 탈출구를 찾을 수 있는 경우

(start에서 레버까지의 이동 거리) + (레버 위치에서 탈출구까지의 이동 거리)를 return

 

만약 레버나 탈출구 둘 중 하나를 찾을 수 없는 경우

-1을 return

 

2. 내가 작성한 코드

from collections import deque

def solution(maps):
    n = len(maps) #세로
    m = len(maps[0]) #가로
    
    start = 0 #start의 위치 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                start = (i,j)

    #처음 위치에서 레버 찾기
    result1 = bfs(start,"L",n,m,maps)
    
    #레버를 찾을 수 없다면 return -1
    if result1 == -1:
        return -1
    else: #레버를 찾을 수 있는 경우
        start = (result1[1],result1[2]) #새로운 시작점은 레버의 위치
        cnt = result1[0] #레버까지의 이동 거리 저장
        result2 = bfs(start,"E",n,m,maps) #레버의 위치에서 시작해서 탈출구 찾기
        if result2 == -1: #탈출구를 찾을 수 없으면 return -1
            return -1
        else: #start에서 레버까지의 이동거리 + 레버에서 탈출구 까지의 이동거리
            return cnt + result2[0]
    
def bfs(start, end, n, m, maps):
    visit = [[0 for i in range(m)] for _ in range(n)]
    visit[start[0]][start[1]] = 1
    queue = deque()
    queue.append((start[0],start[1]))
    
    while queue:
        x,y = queue.popleft()
        dx = [-1,1,0,0]
        dy = [0,0,1,-1]
        
        if maps[x][y] == end:
            print(x,y)
            return visit[x][y]-1, x,y
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            
            if maps[nx][ny] == "X":
                continue
            
            if visit[nx][ny] == 0:
                visit[nx][ny] = visit[x][y] + 1
                queue.append((nx,ny))
    
    return -1