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

문제

---

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

 

• 소요 시간 : 2시간
• 난이도 : LV 3

나의 풀이

---

 

접근 방법

1. S에서 E까지의 최단 경로를 사전순으로 제일 빨리 탐색한다.

• d > l > r > u 가 사전순이기 때문에 아래, 왼쪽, 오른쪽, 위 순으로 BFS를 돌려 최단거리를 찾는다.

2. S에서 E까지의 최단 거리와 k의 차이를 이용해 추가적인 처리를 한다.

• k == S에서 E까지의 최단 거리 : 별도로 추가하지 않고 경로를 반환한다.
• k > S에서 E까지의 최단 거리
  • 차이가 홀수일 경우 : 경로에 영향을 주지 않고 추가로 움직이려면 [아래위, 왼오, 오왼, 위아래] 이렇게 2번씩 움직여야하는데, 홀수일 경우 불가능하므로 impossible을 반환한다. 
  • 차이가 짝수일 경우 : S에서 E까지 가는 경로의 각 점에서 사전순으로 제일 빠른 방향 [아래위, 왼오, 오왼, 위아래] 순으로 갈 수 있는지 체크한 후 문자열을 더해본다. 

ex. [아래위, 왼오, 오왼, 위아래] 순서로 갈 수 있는지 체크

		S
E

제일 빠른 경로 = dll 
1. (2, 3)
아래위(du) 가능 -> du + dll = dudll

2. (3, 3)
아래위(du) 불가능 
왼오(lr) 가능 -> d + lr + ll = dlrll

3. (3, 2)
아래위(du) 불가능 
왼오(lr) 가능 -> dl + lr + l = dllrl

3. (3, 1)
아래위(du) 불가능 
왼오(lr) 불가능
오른왼(rl) 가능 -> dll + rl = dllrl 

가장 사전순으로 빠른 dllrl 

 

=> 다른 방법을 찾아보자 .. 

시간복잡도

1. 최단경로 탐색은 최대 N * M 배열이므로 O(NM)이 소요 

https://www.acmicpc.net/board/view/47137

2. 문자열 돌 때 O(path길이+1) 최대 path길이 : 50 + 50 = 100 

코드

from collections import deque

def get_distance(x1: int, y1: int, x2: int, y2: int):
    return abs(x1 - x2) + abs(y1 - y2)

def get_dir_char(dx: int, dy: int):
    if dx == 1 and dy == 0: 
        return 'd'
    elif dx == -1 and dy == 0: 
        return 'u'
    elif dx == 0 and dy == 1: 
        return 'r'
    elif dx == 0 and dy == -1: 
        return 'l'
    else:
        return None

def move(x: int, y: int, dir: str):
    if dir == 'd':
        return (x+1, y)
    elif dir == 'u':
        return (x-1, y)
    elif dir == 'r':
        return (x, y+1)
    elif dir == 'l':
        return (x, y-1)
    else:
        return None 
    
def solution(n, m, x, y, r, c, k):    
    # 1. 시작점 ~ 끝점 거리 구하기
    # 거리 - k = 홀수 : impossible
    
    if (get_distance(x, y, r, c) - k) % 2 == 1:
        return "impossible"
        
    # 2. 가는 경로 구하기 with BFS
    answer = ''
    
    # 지도 
    map = [['.'] * (m+1) for _ in range(n+1)] 
    map[x][y] = 'S'
    map[r][c] = 'E'

    visited = [[False] * (m+1) for _ in range(n+1)]
    
    # 방향 : 아래 > 왼 > 오 > 위
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]
    
    path = ''
        
    q = deque([])
    # 시작점 
    q.append((x, y, ''))
    
    while q:
        curr_x, curr_y, curr_path = q.popleft()
        visited[curr_x][curr_y] = True

        # 도착
        if curr_x == r and curr_y == c:            
            if len(path) == 0:
                path = curr_path
            else:
                path = min(path, curr_path)
        else:        
            for dir in range(4):
                nx = curr_x + dx[dir]
                ny = curr_y + dy[dir]

                # 범위 체크
                if nx > n or nx <= 0 or ny > m or ny <= 0 or visited[nx][ny]:
                    continue
                    
                q.append((nx, ny, curr_path + get_dir_char(dx[dir], dy[dir])))

    if len(path) == k:
        return path

                
    # 3. 뻘 움직임 추가하기 (아래위, 왼오, 오왼, 위아래)
    # 사전순으로 제일 빠르게 ? 어떻게?...
    
    appended_moves = ['du', 'lr', 'rl', 'ud']

    x_pos = x
    y_pos = y 
    answer = ''   
    index = 0 
    count = int((k-len(path)) / 2)
    
    # S -> E로 문자열대로 가면서 
    for index in range(len(path)+1):  
        # 4방향 체크 후 갈 수 있다면 문자열 추가
        for dir in range(4):
            nx = x_pos + dx[dir]
            ny = y_pos + dy[dir]

            # 범위 초과 
            if nx > n or nx <= 0 or ny > m or ny <= 0:
                continue
            else:          
                new_path = path[:index] + appended_moves[dir] * count + path[index:]          
                # 후 answer와 비교 
                if len(answer) == 0:
                    answer = new_path
                else:
                    answer = min(new_path, answer)
                break
        
        if index < len(path):
            x_pos, y_pos = move(x_pos, y_pos, path[index])
        
        
    return answer

 

결과 : 시간초과 + 실패 

 

실패 이유 분석 

1. 이동 거리가 k보다 큰 경우도 impossible을 반환한다. 

2. 로직을 설계할 때 k와 차이가 2이상의 숫자일 때를 고려하지 못해서, 차이를 2로 나누고 문자열을 추가할 때 그만큼 곱해서 추가해주었었다.. (ex. 차이가 4이면 du * 2 추가)

 

여기서 틀린 것 

차이가 4이면 dudu 일 수도 있고, dduu가 될 수도 있다 .

아래, 왼쪽일 경우 이런식으로 반복하는 게 사전순으로 빠르지만 추가로 갈 수 있는지 더 체크해야한다.

dduu 

llrr 

오른쪽, 위일 경우 이런식으로 반복하는 게 사전순으로 빠르다. 

rlrl

udud

---

다른 사람의 풀이

---

https://cheon2308.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv3-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4

[프로그래머스 Lv3] 파이썬 - 미로 탈출 명령어

 

접근 방법

이제 일반적인 bfs를 돌리며 순회 순서를 d, l, r, u 순서로 방문하는 로직은 동일하다. 
q에 이동횟수를 함께 넣어준다. 
visited 배열을 사용하지 않는다. 

현재까지 이동 거리 + 남은거리가 k보다 크다면 넘어가고, 그렇지 않다면 q에 담아준다.

visited 배열을 사용하지 않기 때문에 시간 초과가 발생할 수 있다.
시간 초과와 사전순 탐색을 해결하기 위하여 d l r u의 방문 순서로 탐색하므로, 최초로 q에 담기는 순간 break를 해준다.
즉, d를 최대한 많이 간 후, l을 최대한 많이 가고 r u가 담기게 된다.

 

시간복잡도

BFS로 O(NM) 소요 

코드

from collections import deque


def is_valid(x: int, y: int, n: int, m: int):
    return 1 <= x <= n and 1 <= y <= m

def get_distance(x1: int, y1: int, r: int, c: int):
    return abs(x1 - r) + abs(y1 - c)

def solution(n, m, x, y, r, c, k):    
    answer = ''

    # 시작점 ~ 끝점 거리 구하기
    distance = get_distance(x, y, r, c)
    
    # k번 내에 이동 불가능한 경우 
    if distance > k or (distance - k) % 2:
        return "impossible"
        
    
    # 방향 : 아래 > 왼 > 오 > 위
    direct = {(1,0):'d', (0,-1):'l', (0,1):'r', (-1,0):'u'}
    q = deque()
    # 시작점 
    q.append((x, y, 0, ''))
    
    while q:
        cx, cy, cnt, route = q.popleft()
        
        # 도착
        if (cx, cy) == (r, c):
            # 남은 거리가 홀수라면 도착지에 k만큼 오지 못한다!
            if (k-cnt) % 2:
                return 'impossible'
            elif k == cnt:
                return route
        
        for dx, dy in direct:
            nx, ny = cx + dx, cy + dy

            # 범위 체크
            if is_valid(nx, ny, n, m):
                # 다음 이동 자리를 보는 것이므로 +1 을 해주어야 함
                if (get_distance(nx, ny, r, c) + cnt + 1) > k:
                    continue
                    
                q.append((nx, ny, cnt+1, route+direct[(dx, dy)]))
                break

    return answer

 

결과 : 정답

 

정리

---

다시 풀어보면 좋을 듯한 문제..

그래도 이제 접근 방법까지는 잘 생각하는 듯 하다.

코드로 구현하는 부분 다른 사람 풀이 많이 보며 더 학습하기!