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

문제

bfs로 풀면되는 문제이다.

출발점-> 레버 + 레버 -> 도착점 

두 합의 최소를 구하면 된다.

 

코드

from collections import deque
def solution(maps):
    answer = 0
    startDot, leverDot, endDot = None, None, None
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] == "S":
                startDot = (i,j)
            elif maps[i][j] == "L":
                leverDot = (i,j)
            elif maps[i][j] == "E":
                endDot = (i,j)
            else:
                continue
                
    startToLever = bfs(maps,startDot, leverDot)
    if startToLever == -1:
        return -1
    leverToEnd = bfs(maps,leverDot, endDot)
    if leverToEnd == -1:
        return -1
    return startToLever + leverToEnd

def bfs(maps, start, end):
    (sR, sC) = start
    mC = [0,1,0,-1]
    mR = [1,0,-1,0]
    q = deque()
    q.append(Dot(sR,sC,0))
    s = set([start])
    while q: 
        cDot = q.popleft()
        if (cDot.r, cDot.c) == end:
            return cDot.cnt
        for i in range(4):
            nR, nC = mR[i] + cDot.r, mC[i] + cDot.c
            if nR < 0 or nR >= len(maps) or nC < 0 or nC >= len(maps[0]):
                continue
            if maps[nR][nC] == "X" or (nR, nC) in s:
                continue
            q.append(Dot(nR,nC,cDot.cnt+1))
            s.add((nR, nC))
    return -1
            
            
class Dot:
    def __init__(self, r, c, cnt):
        self.c = c
        self.r = r
        self.cnt = cnt
        
'''
레버를 당겨야지만 미로르 탈출 가능
탈출할 수 없으면 -1 반환
BFS로 하고, 레버를 지나고 마지막 지점에 도착하면 
갔던 곳 또 갈 수 있어야지
시작점부터, 레버까지 길이 구하고, 레버부터 시작점까지 길이 구하기
'''