[프로그래머스- lv2] 미로 탈출/ 파이썬

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

---

문제 풀이)

문제에서 1칸의 크기는 1X1 크기의 정사각형이다. 간선의 비용이 1이므로 BFS를 이용해 풀어봤다.

문제 해결 아이디어는 다음과 같다.

먼저 레버를 열어서 탈출구를 열수 있고 레버를 열기전 출구여도 지나다닐수 있다 했다.

 

즉 start 노드로부터 end 노드까지 cost를 return 하는 bfs함수를 작성한후

 

BFS('S', 'L') + BFS('L', 'E')의 결과값을 구하면 된다.

 

작성 코드는 다음과 같다.

from collections import deque
def bfs(s, e, maps):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    n = len(maps)
    m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    q = deque()
    flag = False
    for i in range(n):
        for j in range(m):
            if maps[i][j] == s:
                q.append((i, j, 0)) # start node queue에 추가
                visited[i][j] = True # 방문 처리
                flag = True
                break
        if flag:
            break

    while q:
        y, x, cost = q.popleft()
        if maps[y][x] == e:
            return cost
        for i in range(4): # 상, 하, 좌, 우 4가지 방향 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and maps[ny][nx] != 'X': # 갈수 있는 경로에 있는 경우
                if not visited[ny][nx]:
                    q.append((ny, nx, cost+1))
                    visited[ny][nx] = True
    return -1
def solution(maps):
    path1 = bfs('S', 'L', maps) # 시작점부터 레버까지 거리
    path2 = bfs('L', 'E', maps) # 레버부터 출구까지 거리
    if path1 != -1 and path2 != -1:
        return path1 + path2
    return -1