[코딩테스트] 프로그래머스 미로 탈출 파이썬(Python)

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

프로그래머스

from collections import deque
def solution(maps):
    def is_range(x, y):
        if 0 <= x < n and 0 <= y < m:
            return True
        else:
            return False
    def find(start, end):
        visited = [[0 for _ in range(m)] for _ in range(n)]
        dx = [0,0,-1,1]
        dy = [1,-1,0,0]
        q = deque()
        q.append((start['x'], start['y'], 0))
        while q:
            cx, cy, count = q.popleft()
            if cx == end['x'] and cy == end['y']:
                return count
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                if is_range(nx, ny) and visited[nx][ny] == 0 and graph[nx][ny] != 'X':
                    q.append((nx, ny, count+1))
                    visited[nx][ny] = 1
        return -1
    graph = list(map(list, maps))
    n = len(graph)
    m = len(graph[0])
    S = {'x' : 0, 'y' : 0}
    L = {'x' : 0, 'y' : 0}
    E = {'x' : 0, 'y' : 0}
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 'S':
                S['x'] = x
                S['y'] = y
            elif graph[x][y] == 'L':
                L['x'] = x
                L['y'] = y
            elif graph[x][y] == 'E':
                E['x'] = x
                E['y'] = y

    c1 = find(S, L)
    c2 = find(L, E)
    if c1 == -1 or c2 == -1:
        return -1
    return c1 + c2

먼저 solution 내부에 있는 find함수에 대하여 이야기하겠습니다.

 

find함수는 bfs를 구현한 함수이고 아래와 같이 동작합니다.

find함수는 먼저 입력으로 들어오는 시작위치 start의 좌표 x, y로 시작하여 현재위치 cx, cy가 종료위치 end의 x, y와 같아지면 종료하게됩니다.

 

기본적인 bfs의 구조를 가지며 좌표를 탐색할 때마다 count+1을 하여 시간을 증가시킵니다.

 

모든 q를 반복했음에도 end좌표에 도달하지 못한다면 탈출할 수 없다는 의미이기 때문에 -1을 반환합니다.

 

다음은 find함수의 밖으로 나와서 확인해보겠습니다.

 

문제를 해결하는데 사용한 변수는 아래와 같습니다.

• graph : 입력으로 들어오는 maps를 모두 list형태로 바꾸었습니다.
• n : x축의 최대 범위입니다.
• m : y축의 최대 범위입니다.
• S : graph에서 'S'(시작지점)에 해당하는 좌표입니다.
• L : graph에서 'L'(레버)에 해당하는 좌표입니다.
• E : graph에서 'E'(출구)에 대항하는 좌표입니다.

solution의 과정은 아래와 같습니다.

 

먼저 graph를 탐색하면서 시작지점(S), 레버(L), 출구(E)의 위치를 저장합니다.

 

find함수를 사용하여 시작지점(S)으로부터 레버(L)까지의 시간(c1)을 찾습니다.

마찬가지로 레버(L)로부터 출구(E)까지의 시간(c2)를 찾습니다.

 

위에서 구한c1 혹은 c2 에서 -1이 나온다면 -1을 반환합니다.

 

만약 -1로 반환되지 않았다면 c1+c2로 탈출에 필요한 최소 시간을 반환합니다.