프로그래머스 미로 탈출

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한 사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

나의 무지성 풀이

• 이전에 길 찾기 한 거를 2번 하면 되는거 아니냐? 하면서 쭐쭐 짰고 테스트 케이스는 통과.
• 근데 짜면서도 코드가 너무 길어서 안될 줄 알았다.

from collections import deque
    
def solution(maps): # 경유지가 있는 길찾기 문제
    answer = 0
    
    goals = {'S':[0,0],'L':[0,0],'E':[0,0]}
    
    map_size_x = len(maps[0])
    map_size_y = len(maps)
    
    map_data = []
    
    for i in range(map_size_y):
        _tmp = list(maps[i])
        for j in range(map_size_x):
            if _tmp[j] == 'X':
                _tmp[j] = 0
            else:
                _tmp[j] = 1
        map_data.append(_tmp)
        if 'S' in maps[i]:
            goals['S'] = [maps[i].index('S'), i]
        if 'L' in maps[i]:
            goals['L'] = [maps[i].index('L'), i]
        if 'E' in maps[i]:
            goals['E'] = [maps[i].index('E'), i]
        
    def find_way(begin_x, begin_y, goal_x, goal_y):
        x_move = [1, 0, -1, 0]
        y_move = [0, 1, 0, -1]
        
        queue = deque([(begin_x, begin_y, 1)])

        while queue:
            x, y, d = queue.popleft()

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

                if nx > -1 and ny > -1 and nx < map_size_x and ny < map_size_y:
                    if map_data[ny][nx] != 0 or map_data[ny][nx] > d + 1:
                        map_data[ny][nx] = d + 1
                        if nx == goal_x and ny == goal_y:
                            return d + 1

                        queue.append((nx, ny, d + 1))
        return -1

    def draw():
        for i in map_data:
            print(i)
        print
    #draw()
    
    a = find_way(goals['S'][0], goals['S'][1], goals['L'][0], goals['L'][1])
    b = find_way(goals['L'][0], goals['L'][1], goals['E'][0], goals['E'][1])
    
    if min(a, b) == -1:
        return -1
    
    return a + b - 2

• 답은 맞지만 시간 초과입니다. 휴먼.
• 왠지 S랑 E가 붙어있고, L은 끝에 있을 것 같다.
• 두번의 길찾기로 속도가 안나온다면 한번의 길찾기로 두개 위치를 찾아야 한다.
• 내가 생각하는 그거 맞지???

정확성  테스트
테스트 1 〉	통과 (2.63ms, 10.4MB)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	통과 (27.77ms, 12.3MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	통과 (51.02ms, 13.9MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (0.27ms, 10.3MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)
테스트 16 〉	실패 (시간 초과)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	실패 (시간 초과)
테스트 22 〉	실패 (시간 초과)
테스트 23 〉	통과 (0.09ms, 10.3MB)

• 그래서 소스를 수정했는데 틀림. 디큐 그대로 수정했는데 틀림.
  • draw_map( ) 함수 만들어서 보니까 덮어쓰기가 됨.
  • 아무래도 우선순위 큐를 쓰는게 맞지 싶음.
• heapq로 바꾸고 소스 수정하고 또 수정하고 해도 하나가 안풀려서 혹시나 해서 limit를 늘렸더니 해결됨.
  • 내가 푼 방식은 기존 길찾기와 동일한데,
  • 레버 위치에서 범위를 넓히면서 시작위치와 도착위치를 찾고,
  • 둘 다 찾은 경우 레버위치에서 각각의 위치(시작, 도착)까지의 거리를 합해서 리턴하는 방식으로 풀었다.

import heapq
    
def solution(maps): # 경유지가 있는 길찾기 문제
    pq = []
    dist = 0
    map_size_y, map_size_x = len(maps), len(maps[0])
    map_data, sp, lp, ep = [], [], [], []
    limit = map_size_y * map_size_x
    is_find = [False, False]
    
    for i in range(map_size_y):
        _t = list(maps[i])
        for j in range(map_size_x):
            a = _t[j]
            if   a == 'E': ep = [j,i]
            elif a == 'L': lp = [j,i]
            elif a == 'S': sp = [j,i]
            if   a == 'X': _t[j] = -1
            else: _t[j] = limit
        map_data.append(_t)
        
    distance_to_start = limit
    distance_to_ep = limit

    heapq.heappush(pq, [dist, (lp[0], lp[1])])
    
    while len(pq) > 0:
        _pq = heapq.heappop(pq)
        dist, x, y = _pq[0], _pq[1][0], _pq[1][1]
        
        if x == sp[0] and y == sp[1]:
            distance_to_start = min(distance_to_start, dist)
            is_find[0] = True
        if x == ep[0] and y == ep[1]:
            distance_to_ep = min(distance_to_ep, dist)
            is_find[1] = True
        if is_find == [True, True]:
            return distance_to_start + distance_to_ep

        if map_data[y][x] > dist:
            map_data[y][x] = dist
            dist += 1
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx and nx < map_size_x and 0 <= ny and ny < map_size_y:
                    heapq.heappush(pq, [dist, (nx, ny)])
        
    return -1

• 속도도 맨 처음 것보다 빠름.
• 근데 이게 12번째 수정한 소스임 ㅋㅋㅋ
• 비뇌지컬 무지성 코딩이 힘든 이유... 손이 뻐근함.

정확성  테스트
테스트 1 〉	통과 (0.07ms, 10.3MB)
테스트 2 〉	통과 (0.24ms, 10.3MB)
테스트 3 〉	통과 (0.22ms, 10.1MB)
테스트 4 〉	통과 (0.21ms, 10.3MB)
테스트 5 〉	통과 (0.33ms, 10.2MB)
테스트 6 〉	통과 (0.21ms, 10.4MB)
테스트 7 〉	통과 (3.10ms, 10.2MB)
테스트 8 〉	통과 (5.27ms, 10.1MB)
테스트 9 〉	통과 (0.06ms, 10.1MB)
테스트 10 〉	통과 (0.02ms, 10.3MB)
테스트 11 〉	통과 (1.57ms, 10.3MB)
테스트 12 〉	통과 (11.25ms, 10.4MB)
테스트 13 〉	통과 (10.17ms, 10.3MB)
테스트 14 〉	통과 (11.37ms, 10.3MB)
테스트 15 〉	통과 (0.85ms, 10.5MB)
테스트 16 〉	통과 (29.50ms, 10.3MB)
테스트 17 〉	통과 (34.61ms, 10.4MB)
테스트 18 〉	통과 (0.83ms, 10MB)
테스트 19 〉	통과 (0.26ms, 10.2MB)
테스트 20 〉	통과 (17.84ms, 10.3MB)
테스트 21 〉	통과 (3.22ms, 10.2MB)
테스트 22 〉	통과 (0.22ms, 10.4MB)
테스트 23 〉	통과 (0.09ms, 10.4MB)

• 이거 좀 어려웠는데... 암튼 해결.
• 3시간 동안 고생했다고 +3점 주는 것 같다.

고수의 풀이

• 근데 다른 사람들 풀이 보니까, 디큐로 두번 찾아서 해결했는데...?
• 이게 되는건데 내가 바본가?

from collections import deque

def solution(maps):
    pos=[-1,-1,0]
    flag=False
    dir=[(-1,0),(0,1),(1,0),(0,-1)]

    # find start
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j]=='S':
                pos=[i,j,0]
    #find lever
    queue=deque([pos])
    visited=[[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[pos[0]][pos[1]]=1

    while queue:
        temp=queue.popleft()
        if maps[temp[0]][temp[1]]=="L":
            pos=temp
            flag=True
            break
        for d in dir:
            dx=temp[0]+d[0]
            dy=temp[1]+d[1]
            if dx>=0 and dx<len(maps) and dy>=0 and dy<len(maps[0]):
                if maps[dx][dy]!='X' and visited[dx][dy]==0:
                    queue.append([dx,dy,temp[2]+1])
                    visited[dx][dy]=1
    if flag==False:
        return -1

    #find exit
    queue=deque([pos])
    visited=[[0 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[pos[0]][pos[1]]=1

    while queue:
        temp=queue.popleft()
        if maps[temp[0]][temp[1]]=="E":
            return temp[2]
            break
        for d in dir:
            dx=temp[0]+d[0]
            dy=temp[1]+d[1]
            if dx>=0 and dx<len(maps) and dy>=0 and dy<len(maps[0]):
                if maps[dx][dy]!='X' and visited[dx][dy]==0:
                    queue.append([dx,dy,temp[2]+1])
                    visited[dx][dy]=1
    return -1

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.1MB)
테스트 2 〉	통과 (0.13ms, 10.3MB)
테스트 3 〉	통과 (0.19ms, 10.2MB)
테스트 4 〉	통과 (0.28ms, 10.4MB)
테스트 5 〉	통과 (0.21ms, 10.2MB)
테스트 6 〉	통과 (0.12ms, 10.2MB)
테스트 7 〉	통과 (2.44ms, 10.3MB)
테스트 8 〉	통과 (3.93ms, 10.2MB)
테스트 9 〉	통과 (0.06ms, 10.4MB)
테스트 10 〉	통과 (0.02ms, 10.2MB)
테스트 11 〉	통과 (0.84ms, 10.1MB)
테스트 12 〉	통과 (5.64ms, 10.4MB)
테스트 13 〉	통과 (6.68ms, 10.2MB)
테스트 14 〉	통과 (5.06ms, 10.2MB)
테스트 15 〉	통과 (0.64ms, 10.3MB)
테스트 16 〉	통과 (11.76ms, 10.4MB)
테스트 17 〉	통과 (18.72ms, 10.4MB)
테스트 18 〉	통과 (0.44ms, 10.4MB)
테스트 19 〉	통과 (0.25ms, 10.2MB)
테스트 20 〉	통과 (11.07ms, 10.5MB)
테스트 21 〉	통과 (2.85ms, 10.2MB)
테스트 22 〉	통과 (0.27ms, 10.2MB)
테스트 23 〉	통과 (0.05ms, 10.2MB)

• 이것도 빠르다. 그냥 두번 찾아도 되는구나...
• 다음에 짤 때는 이렇게 짜야지.
• 분명히 나도 처음엔 이렇게 짤려고 했던 것 같은데 머리가 안되서... ㅡ.ㅡ; 

def solution(maps):
    answer = 0
    x, y, d = None, None, 0
    n = len(maps)
    m = len(maps[0])
    chk = [[False for _ in range(m)] for _ in range(n)]
    dd = [[0, 1], [1, 0], [-1, 0], [0, -1]]

    for i, x in enumerate(maps):
        for j, y in enumerate(x):
            if y == 'S':
                sx = i
                sy = j
                chk[i][j] = True


    def get_d(sx, sy, target, flag):
        q = [[sx, sy, 0]]
        chk = [[False for _ in range(m)] for _ in range(n)]
        chk[sx][sy] = True
        while q:
            x, y, d = q.pop(0)
            if maps[x][y] == target:
                return [x, y, d]

            for dx, dy in dd:
                nx = x + dx
                ny = y + dy

                if not (0 <= nx < n and 0 <= ny < m) or chk[nx][ny] or maps[nx][ny] == 'X':
                    continue

                q.append([nx, ny, d + 1])
                chk[nx][ny] = True
        return [-1, -1, -1]
    x1, y1, d1 = get_d(sx, sy, 'L', False) 
    if x1 == -1:
        return -1
    x2, y2, d2 = get_d(x1, y1, 'E', True)
    if x2 == -1:
        return -1
    return d1 + d2

정확성  테스트
테스트 1 〉	통과 (0.09ms, 10.1MB)
테스트 2 〉	통과 (0.17ms, 10.1MB)
테스트 3 〉	통과 (0.13ms, 10.2MB)
테스트 4 〉	통과 (0.20ms, 10.1MB)
테스트 5 〉	통과 (0.26ms, 10.1MB)
테스트 6 〉	통과 (0.16ms, 10.2MB)
테스트 7 〉	통과 (2.04ms, 10.2MB)
테스트 8 〉	통과 (3.14ms, 10.2MB)
테스트 9 〉	통과 (0.04ms, 10MB)
테스트 10 〉	통과 (0.03ms, 10.2MB)
테스트 11 〉	통과 (0.81ms, 10.2MB)
테스트 12 〉	통과 (5.40ms, 10.3MB)
테스트 13 〉	통과 (4.85ms, 10.3MB)
테스트 14 〉	통과 (4.68ms, 10.1MB)
테스트 15 〉	통과 (0.76ms, 10.2MB)
테스트 16 〉	통과 (13.90ms, 10.3MB)
테스트 17 〉	통과 (11.47ms, 10.3MB)
테스트 18 〉	통과 (0.32ms, 10.1MB)
테스트 19 〉	통과 (0.25ms, 10.2MB)
테스트 20 〉	통과 (9.89ms, 10.3MB)
테스트 21 〉	통과 (2.57ms, 10.1MB)
테스트 22 〉	통과 (0.31ms, 10.2MB)
테스트 23 〉	통과 (0.06ms, 10.2MB)

만약 이런 문제 다시 풀기 한다면,

• 색칠하기 알고리즘으로 각 포인트가 서로 연결되어 있는지도 찾으면서,
• 탐색 범위 넓히면서 가능/안가능 체크하면서
• 두개의 배열을 새로 만들고,
• 범위 확인해서 연결 안되어 있으면 종료
• 탐색 범위에서 각 포인트 좌표에 들어있는 값을 가져와서 리턴하는 방식으로 해봐야지...

https://ko.m.wikipedia.org/wiki/플러드_필

플러드 필 - 위키백과, 우리 모두의 백과사전

즐거운 무지성 코딩 생활~!