미로 탈출

 

입출력 예 #1

주어진 문자열은 다음과 같은 미로

 

다음과 같이 이동시 가장 빠른 시간에 탈출 가능

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

 

입출력 예 #2

주어진 문자열은 다음과 같은 미로

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

코딩테스트 연습 - 미로 탈출 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

from collections import deque
import copy
def solution(maps):
    answer = 0
    rt_maps = []
    start_pt = []
    l_pt = []
    e_pt = []
    move = [(1,0), (-1,0), (0,1), (0,-1)]
    # 초기 맵을 만들어준다
    for i in range(len(maps)):
        rt_maps.append(list(maps[i]))
        # 시작,레버,끝 좌표를 구해준다
        if 'S' in list(maps[i]):
            start_pt = [i,list(maps[i]).index('S')]
        if 'L' in list(maps[i]):
            l_pt = [i,list(maps[i]).index('L')]
        if 'E' in list(maps[i]):
            e_pt = [i,list(maps[i]).index('E')]
    #print(rt_maps)
    #print(start_pt)
    #print(l_pt)
    #print(e_pt)
    
    # bfs를 돌릴 맵을 만들고, 시작좌표 0으로 치환
    new_maps = copy.deepcopy(rt_maps)
    new_maps[start_pt[0]][start_pt[1]] = 0
    queue = deque()
    queue.append(start_pt)
    #print(new_maps)
    # 레버가 있는 곳까지 bfs돌며 이동시 1초 를 늘려준다
    while queue: 
        x,y, = queue.popleft()
        if [x,y]==l_pt:
            break
        for i in move:
            new_x = x+i[0]
            new_y = y+i[1]
            if 0<=new_x<len(new_maps) and 0<=new_y<len(new_maps[0]) and new_maps[new_x][new_y] in ['O','L','E'] and [new_x,new_y] not in queue:
                new_maps[new_x][new_y] = new_maps[x][y]+1
                queue.append([new_x,new_y])
    #print(new_maps)
    # 레버까지 갈수있으면 걸린 시작을 answer에 더하고
    # 못가면 바로 -1을 리턴한다
    if new_maps[l_pt[0]][l_pt[1]] != 'L':
        answer += new_maps[l_pt[0]][l_pt[1]]
    else:
        return -1
    
    # 최종 bfs를 위한 맵을 만들어줌, 레버 좌표 0으로 치환
    new_result_maps = copy.deepcopy(rt_maps)
    new_result_maps[l_pt[0]][l_pt[1]] = 0
    queue = deque()
    queue.append(l_pt)
    # 레버 좌표에서 시작하여 출구까지 bfs를 시작
    while queue:
        x,y = queue.popleft()
        if [x,y]==e_pt:
            break
        for i in move:
            new_x = x+i[0]
            new_y = y+i[1]
            if 0<=new_x<len(new_result_maps) and 0<=new_y<len(new_result_maps[0]) and new_result_maps[new_x][new_y] in ['O','S','E'] and [new_x,new_y] not in queue:
                new_result_maps[new_x][new_y] = new_result_maps[x][y]+1
                queue.append([new_x,new_y])
    #print(new_result_maps)
    # 출구 까지 갈수 있으면 걸린시간 answer에 더하고
    # 못가면 -1 리턴
    if new_result_maps[e_pt[0]][e_pt[1]] != 'E':
        answer += new_result_maps[e_pt[0]][e_pt[1]]
    else:
        return -1
     
    # 최종적으로 걸린시간을 리턴한다
    return answer