파이썬)미로 탈출

 

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

프로그래머스

 

 

from collections import deque
import copy


def solution(maps):

    s = []
    l = []
    exit = []

    answer = 0
    visit = [[int(0) for _ in range(len(maps[0]))] for _ in range(len(maps))]

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                s = [i, j]
                q = deque()  # q 변수 정의 및 초기화
                q.append((i, j))

            elif maps[i][j] == 'E':
                exit = [i, j]
            elif maps[i][j] == 'L':
                l = [i, j]
    # visit[s[0]][s[1]] = True
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]

    def bfs1(w, h, coin):
        bfs1visit = copy.deepcopy(visit)
        q = deque()  # q 변수 정의 및 초기화
        q.append((w, h))

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y

                if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                    if maps[nx][ny] == 'O' or maps[nx][ny] == 'E':
                        if bfs1visit[nx][ny] == 0:
                            bfs1visit[nx][ny] = bfs1visit[x][y] + 1
                            q.append((nx, ny))
                    elif maps[nx][ny] == 'L':
                        return bfs1visit[x][y] + 1

        return -1

    lebor = bfs1(s[0], s[1], 0)

    if lebor == -1:
        return -1

    visit[l[0]][l[1]] = lebor

    def bfs(w, h):
        q = deque()  # q 변수 정의 및 초기화
        q.append((w, h))

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = dx[i] + x
                ny = dy[i] + y

                if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                    if maps[nx][ny] == 'O' or maps[nx][ny] == 'S':
                        if visit[nx][ny] == 0:
                            visit[nx][ny] = visit[x][y] + 1
                            q.append((nx, ny))
                    elif maps[nx][ny] == 'E':
                        return visit[x][y] + 1

        return -1

    answer = bfs(l[0], l[1])
    return answer

 

문제는 출구까지 몇초가 걸리는지 찾는 전형적인 BFS알고리즘을 이용해 풀어야하는 문제이다.

다만 생각해야할 점이 몇가지 있었다.

1. 시작위치는 'S'에서 시작한다. 
2. 레버('L')를 눌러야만 출구('E')가 열린다.
3. 레버를 누르기 전이라면 출구를 통과할 수 있다.(말 그대로 통과다. 탈출이 아니라 통로처럼 이용할 수 있다.)
4. 만일 탈출할 수 없다면 -1을 리턴한다.

문제는 잘 생각해보면 출구 -> 레버 -> 탈출 순으로 진행된다.

레버까지의 최소 시간을 구한 후, 다시 레버에서 출구까지의 시간을 구하면 된다.

그렇기때문에 우선 레버까지의 최소 시간을 구한 후, 다시 레버부터 시작해 탈출구까지의 최소시간을 더하면 된다.

하지만 고려해야할 사항이 몇가지 있다.

• 시작위치는 maps[0][0]로 고정이 아니다. 마찬가지로 레버인 'L'과 출구인 'E'의 위치도 테스트케이스마다 랜덤이다.
• maps는 정사각형이 아니다.
• 레버를 누르기 전에 출구를 통로처럼 통과할 수 있다면, 마찬가지로 레버를 눌렀으면 시작위치를 통로처럼 통과할 수 있다.
  예를들어 maps[0][0] = 'E', maps[0][1] = 'S' maps[0][2] = 'L'과 같이 레버를 누른 후 반드시 출구를 다시 밟아야할 경우가 생긴다. (이 조건 때문에 맞왜틀이 30분간 지속되었다.

따라서 레버까지의 최소시간을 구하는 과정에서 다음칸이 통로인지 벽인지 확인하는 조건문에 maps[nx][ny] == 'E' 라는, 탈출구인지(레버를 누르기 전이니 탈출구를 통로처럼 이용할 수 있다.)를 확인하는 조건문을 달아야하고,

마찬가지로 레버부터 출구까지의 시간을 구하는 과정의 조건문에서 maps[nx][ny] == 'S'와 같이 시작위치를 체크해야한다.