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

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

프로그래머스

---

python

from collections import deque
def solution(maps):
    answer = 0
    
    row = len(maps)
    col = len(maps[0])
    
    # 출발점, 레버, 출구 위치 찾기
    q = deque()
    sx, sy, lx, ly, ex, ey = 0,0,0,0,0,0
    for i in range(row):
        if "S" in maps[i]:
            sx = i
            sy = maps[i].index("S")
        if "L" in maps[i]:
            lx = i
            ly = maps[i].index("L")
        if "E" in maps[i]:
            ex = i
            ey = maps[i].index("E")
    
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    
    # 출발점 -> 레버 bfs
    visited = [[0 for j in range(col)] for i in range(row)]
    count = [[0 for j in range(col)] for i in range(row)]
    q.append((sx,sy))
    while q:
        x, y = q.popleft()
        if visited[x][y] == 1:
            continue
        visited[x][y] = 1
        if maps[x][y] == "L":
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<row and 0<=ny<col:
                if maps[nx][ny] != "X":
                    q.append((nx,ny))
                    count[nx][ny] = count[x][y] + 1
    cnt = count[lx][ly]
    
    if cnt == 0:
        return -1
    
    # visited, count 초기화
    for i in range(row):
        for j in range(col):
            visited[i][j] = 0
            count[i][j] = 0
    # q 초기화
    q.clear()
    
    # 레버 -> 출구 bfs
    q.append((lx,ly))
    while q:
        x, y = q.popleft()
        if visited[x][y] == 1:
            continue
        visited[x][y] = 1
        if maps[x][y] == "E":
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<row and 0<=ny<col:
                if maps[nx][ny] != "X":
                    q.append((nx,ny))
                    count[nx][ny] = count[x][y] + 1
    cnt += count[ex][ey]
    
    if visited[ex][ey] == 0:
        return -1
    return cnt