프로그래머스 : 미로찾기

본격 미로찾기 문제풀기!
하 이 문제는 시간초과 때문에 골머리를 많이 앓았다..
문자열로 들어오는 입력은 미로에 대한 표현이다. 입력으로부터 레버를 한번 밟고, 이후에 출구로 탈출한다는 컨셉의 문제이다. 레버를 밟기 전엔 출구 블록(E)도 밟을 수 있으나, 탈출하는 것은 아니다.

즉, 시작(S)에서 레버(L)까지를 찾아간 후 레버(L)에서 출구(E)까지 찾아가야 한다.

그렇다면 어떻게 탐색하는게 좋을까? 고민해봐야한다.
DFS로 해보려니 각 경로별 걸리는 시간을 비교해 그 중 적은 시간인 경로를 골라 출력 해야한다. 이러면 전체 경우의 수를 다 고려하게 되어 연산량이 많아질거 같아..
인접 노드의 방문 여부를 파악해 가능 노드만을 방문하다가 목적지 노드를 만나면 종료하는 BFS방식으로 해보기로 했다.

bfs method

탐색의 컨셉은 시작위치와 종료지점(문자)를 인자로 받아 종료 지점의 문자위치를 방문하면 종료하도록 하였다.
미로에서는 상하좌우로만 이동이 가능하므로

(1,0) (-1,0) (0,1) (0,-1)

해당 수만큼 나아간 위치가 방문 노드의 인접 노드가 되겠다!

우선 구현한 코드는 이러하다.

def bfs(maps, start_pos, end_char):
    from collections import deque
    sr ,sc= start_pos[0], start_pos[1]
    c = [1, -1, 0, 0]
    r = [0, 0, -1, 1]
    C, R = len(maps[0]), len(maps)
    visited = set()
    
    will_visit = deque([(sr,sc,0)]) #(start_pos, time)
    
    #bfs 
    while will_visit :
        vr, vc , time= will_visit.popleft()
        if (vr, vc) in visited: continue #방문여부 체크
        visited.add((vr,vc))
        
        for dr, dc in zip(r,c):
            nr, nc = vr + dr, vc + dc
            #maps 내 좌표인지 확인
            if 0<=nr<R and 0<=nc<C:
            	if maps[nr][nc] == end_char : return time + 1
            	if maps[nr][nc] == 'X': continue
                    will_visit.append((nr,nc, time + 1))
               
    return -1 

새로운 좌표를 nr,nc라고 하면, maps내 사용할 수 있는 좌표인지 확인한 후(조건문) 새로운 좌표가 종료지점 문자나, 방문할 수 없는 문자(X)를 가리키면 리턴 또는 종료를 하도록 하였다.

방문여부 체크를 처음엔 maps크기로 두어 미방문을 -1, 방문 시 현재 소요된 시간을 기록하여 넣었다. 방문한 위치가 -1이 아니면 방문한 이력이 있으므로 방문하지 않도록 말이다.
하지만 이 방법에서 시간 업데이트 때마다 위치 접근 + 기록으로 인해 시간초과가 발생한 것 같다.

따라서 set()을 활용해 방문여부를 체크했다.

sol

def solution(maps):
    # start
    for i in range(len(maps)):
        if 'S' in maps[i]:
            start_pos = (i, maps[i].index('S'))
        if 'L' in maps[i]:
            lever_pos = (i, maps[i].index('L'))
            
    time1 = bfs(maps,start_pos, 'L')
    if time1 == -1: return -1
    time2 = bfs(maps, lever_pos, 'E')
    if time2 == -1: return -1 
    
    return time1 + time2

bfs함수를 시작좌표와 종료문자만을 받기 때문에, 두 시작지점인 S와 L의 위치를 찾아 기록하였다. 이후 두번의 탐색을 거쳐 나온 시간들을 합해 최종 출력하였다.