[프로그래머스][python]미로 탈출 명령어

문제

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

소스코드

from collections import deque
def solution(n, m, x, y, r, c, k):
    answer = 'impossible'
    
    q = deque()
    q.append([x,y,0,''])
    
    dx = [1,0,0,-1]
    dy = [0,-1,1,0]
    dic = {0:'d',1:'l',2:'r',3:'u'}

    while q:
        xx,yy,cnt,arr = q.popleft()
        if cnt > k:
            continue
        if cnt == k:
            if (xx == r and yy == c):
                answer = arr
                break
        for s in range(4):
            sx = xx + dx[s]
            sy = yy + dy[s]
            if sx <= 0 or sx > n or sy <=0 or sy > m:
                continue
            if abs(sx - r) + abs(sy - c) + cnt + 1 > k:
                continue       
            q.append([sx,sy,cnt+1,arr+dic[s]])
            break
                
                   
    return answer

설명

BFS를 사용해서 목적지까지 가는 최단거리의 경로를 표현해야하는 문제이다.

미로를 탈출하는 조건은 아래와 같다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

2 번 조건에 의해 visited 를 체크하지 않고 최단거리를 찾아야한다고 생각할 수 있다. 그러면 시간초과를 어떤식으로 방지할 수 있을까를 생각해야한다. 아래는 내가 시간초과를 피하기 위해 생각한 방법이다.

• bfs탐색시 queue에 (x,y,cnt) cnt는 그동안 움직인 이동횟수이다. 이동횟수가 k 이상이면 continue 처리해준다.
• 새로운 좌표를 queue에 넣을 때 (이동할 좌표와 목적지의 좌표의 거리) + 현재까지 움직인 cnt + 1 (새로운 이동 좌표로 움직이면 1 추가됨)을 계산했을 때 k가 넘어버리면 탐색하지 않는다. 어짜피 의미없는 움직임 이기 때문이다. 미래의 경우를 미리 계산해서 제거해준다.

3번조건에 의해 경로를 처리해야한다. 아래는 이 조건을 만족하면서 시간초과를 피하기 위해 생각한 방법이다.

• 탐색을 사전순으로 한다. dic에 사전순으로 정의해두었다. 그냥 4개밖에 안되니까 직접 설정한다. 그래서 탐색을 할 때 조건에 맞는 경우가 나오면 q에 넣고 바로 break로 나머지는 하지 않는다. 어짜피 사전순이기 때문에 뒤에 있는 경우를 탐색하는건 조건에 맞지 않는다.
• bfs는 최단거리를 탐색하는 알고리즈이다. 그러기 때문에 조건에 맞는 답이 나오면 바로 return 처리해주면 된다.

 

후기

            if abs(sx - r) + abs(sy - c) + cnt + 1 > k:
                continue

미래 경우의 수를 생각해주지 않아서 시간초과가 발생했다. 또 사전순으로 처리하면 바로 break처리해주면 되는데 처리를 안해줘서 시간초과가 났다 😭

 

230901 복습 기록

from collections import deque
def solution(n, m, x, y, r, c, k):
    answer = 'impossible'

    dd = ["d","l","r","u"]
    dx = [1,0,0,-1]
    dy = [0,-1,1,0]
    
    q = deque()
    q.append([x,y,0,""])
    
    while q:
        x1,y1,cnt,tmp = q.popleft()
        if (x1 == r and y1 == c) and cnt == k:
            answer = tmp
            break
            
        if cnt >= k:
            continue
            
        for kk in range(4):
            xx = x1 + dx[kk]
            yy = y1 + dy[kk]
            if 0<xx<=n and 0<yy<=m:
                if abs(xx-r) + abs(yy-c) + cnt + 1 <= k:
                    q.append([xx,yy,cnt+1,tmp+dd[kk]])
                    break
                               
    return answer

방문처리를 하지 않고 시간초과를 예방하는 방법

1. 예상경로 + 움직임 횟수를 사전에 예측한 후 안되면 탐색 후보에 넣지 않는다.

현재 경로에서 목적지 까지 위치 + 지금까지 이동한 경로 + 지금 움직일 1 카운트를 더했는데 K 보다 크면 하나마나임 

if abs(xx-r) + abs(yy-c) + cnt + 1 <= k:

2. 탐색 후보가 되면 바로 break 처리를 해준다.

사전순으로 가장 빠른 경로가 답이 된다. 사전순으로 탐색하면서 후보가 나오면 바로 break 해서 다음 항목은 탐색하지 않는다

d ~ 로 시작된 경로는 r ~ 경로보다 무조건 답이 되기 때문

["d","l","r","u"]

 

break 를 안해서 애를 좀 먹었다 😢