[프로그래머스] 미로 탈출 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

미로를 최적의 경로로 탈출하는 문제는 대부분 BFS 알고리즘으로 해결할 수 있다.

해당 문제는 레버가 존재하는데, 이 때문에 BFS 알고리즘을 두 번 사용해야 한다.

우선 레버를 먼저 당겨야 하므로 시작 위치부터 레버의 위치까지 이동하며 최적의 경로를 찾고, 다음으로 레버의 위치부터 출구의 위치까지 이동하며 최적의 경로를 찾아 두 최적의 경로를 합산하여 최종 결과를 도출한다.

두 가지 경로 중 하나라도 결과가 나오지 않는다면 미로를 탈출할 수 없다는 것이다.

 

1. BFS 알고리즘을 구현한 함수에서 사용할 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 입력으로 받는 maps 리스트의 각 문자열을 문자의 리스트로 분리해 2차원 리스트로 저장한다. graph = [list(m) for m in maps]
3. BFS 알고리즘을 구현하는 함수를 생성한다. def bfs(start, end)
   1. 미로를 탐색하며 각 위치를 한 번씩만 거치고, 각 위치까지 이동하는 최소 거리를 저장할 2차원 리스트를 생성한다. visited = [[0 for _ in range(M)] for _ in range(N)]
   2. 이동 가능한 위치를 저장할 deque 자료구조를 생성한다. queue = deque()
   3. 시작 위치를 queue 자료에 추가한다. queue.append(start)
   4. 이동 가능한 위치가 존재하면 반복한다. while (queue)
      1. 현재 위치의 좌표를 queue의 제일 앞 원소를 불러온다. now = queue.popleft()
      2. 이동 가능한 4가지 방향을 하나씩 불러오며 for i in range(len(move))
         1. 다음으로 이동할 행 위치를 저장한다. nextRow = now[0] + move[i][0]
         2. 다음으로 이동할 열 위치를 저장한다. nextCol = now[1] + move[i][1]
         3. 만약 다음으로 이동할 위치가 지도 안에 있고, 아직 방문하지 않은 위치이며, 갈 수 있는 위치라면 if (0 <= nextRow < N) and (0 <= nextCol < M) and (not visited[nextRow][nextCol]) and (graph[nextRow][nextCol] != 'X')
            1. 각 위치까지 이동하는 최소 거리를 저장하는 리스트의 다음 위치 값을 현재 위치 값에 1을 더하여 수정한다. visited[nextRow][nextCol] = visited[now[0]][now[1]] + 1
            2. 다음 위치를 리스트로 묶어 queue에 추가한다. queue.append([nextRow, nextCol])
   5. 더 이상 이동할 수 없어 while 문이 종료되면 끝지점의 거리 값을 반환한다. return visited[end[0]][end[1]]
4. 지도의 세로 길이를 저장한다. N = len(graph)
5. 지도의 가로 길이를 저장한다. M = len(graph[0])
6. 한 행씩 살펴보며 for row in range(len(graph))
   1. 만약 해당 행에 S가 있다면, 해당 위치의 좌표를 시작 위치의 좌표로 저장한다. if ('S' in graph[row]): start = [row, graph[row].index('S')]
   2. 만약 해당 행에 L이 있다면, 해당 위치의 좌표를 레버 위치의 좌표로 저장한다. if ('L' in graph[row]): lever = [row, graph[row].index('L')]
   3. 만약 해당 행에 E이 있다면, 해당 위치의 좌표를 출구 위치의 좌표로 저장한다. if ('E' in graph[row]): end = [row, graph[row].index('E')]
7. 각 위치에서 4가지 방향으로 이동할 수 있으므로 4방향으로 이동할 행과 열의 변환 값을 저장한 리스트를 생성한다. move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
8. BFS 알고리즘을 활용해 시작 위치에서 레버의 위치까지의 최단 경로를 저장한다. distance1 = bfs(start, lever)
9. BFS 알고리즘을 활용해 레버의 위치에서 출구의 위치까지 최단 경로를 저장한다. distance2 = bfs(lever, end)
10. 만약 두 거리 중 하나라도 0의 값이라면 정답에 -1을 저장한다. if (distance1 == 0) or (distance2 == 0): answer = -1
11. 그게 아니라면 두 거리를 더한 결과를 정답에 저장한다. else: answer = distance1 + distance2

3. 소스코드

from collections import deque

def solution(maps):
    answer = 0
    
    graph = [list(m) for m in maps]

    def bfs(start, end):
        visited = [[0 for _ in range(M)] for _ in range(N)]
        queue = deque()
        queue.append(start)
        
        while (queue):
            now = queue.popleft()
            for i in range(len(move)):
                nextRow = now[0] + move[i][0]
                nextCol = now[1] + move[i][1]
                if (0 <= nextRow < N) and (0 <= nextCol < M) and (not visited[nextRow][nextCol]) and (graph[nextRow][nextCol] != 'X'):
                    visited[nextRow][nextCol] = visited[now[0]][now[1]] + 1
                    queue.append([nextRow, nextCol])
    
        return visited[end[0]][end[1]]
    
    N = len(graph)
    M = len(graph[0])
    
    for row in range(len(graph)):
        if ('S' in graph[row]):
            start = [row, graph[row].index('S')]
        if ('L' in graph[row]):
            lever = [row, graph[row].index('L')]
        if ('E' in graph[row]):
            end = [row, graph[row].index('E')]
             
    move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    distance1 = bfs(start, lever)
    distance2 = bfs(lever, end)

    if (distance1 == 0) or (distance2 == 0):
        answer = -1
    else:
        answer = distance1 + distance2

    return answer