[프로그래머스] lv.2 미로 탈출 python 풀이

S (시작위치) 에서부터 L (레버위치)까지 찾는 bfs 1회,

L (레버위치)에서 E (출구위치)까지 찾는 bfs 1회

수행하여 둘 중에 하나라도 -1 (탐색불가)인 경우 -1 리턴

bfs 개념)

https://cccaaa.tistory.com/22

넓이우선탐색(bfs) 동작과정

문제)

코드)

import collections 

def bfs(start_x, start_y, target_x, target_y, MAP):
    move = {(-1,0),(0,1),(1,0),(0,-1)}
    
    q = collections.deque()
    q.append((start_x, start_y, 0)) # cnt : 0
    
    visited = [[0 for _ in range(len(MAP[0]))] for _ in range(len(MAP))]
    visited[start_x][start_y] = 1
    
    while q:
        x, y, cnt = q.popleft()
        if x == target_x and y == target_y:
            return cnt
        
        for tx, ty in move:
            nx = tx + x
            ny = ty + y
            
            if 0<=nx<len(MAP) and 0<=ny<len(MAP[0]) and MAP[nx][ny] != 'X' and visited[nx][ny] != 1:
                visited[nx][ny] = 1
                q.append((nx,ny,cnt+1))
                
    return -1
    

def solution(maps):
    total = 0
    
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] == 'S':
                sx, sy = i,j
            if maps[i][j] == 'L':
                lx, ly = i,j
            if maps[i][j] == 'E':
                ex, ey = i,j
            

    # 레버찾고
    before = bfs(sx, sy, lx, ly, maps)
    # 출구 찾기
    after = bfs(lx, ly, ex, ey, maps)
    
    if before == -1 or after == -1: 
        return -1
    
    return after + before