[Programmers] level3 - 미로 탈출 명령어 (Python) : 2023 KAKAO BLIND RECRUITMENT

▶미로 탈출 명령어 - 2023 KAKAO BLIND RECRUITMENT (level 3)

2023 kakao blind

▶문제

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

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

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. '.'은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해 주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

 

▶입출력 예

입출력 예

입출력 예 #1
문제 예시와 동일합니다.

 

입출력 예 #2
미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

 

입출력 예 #3

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

따라서 "impossible"을 return 해야 합니다.

728x90

▶풀이

원래 bfs를 이용해서 문제를 풀었다.

생각보다 조건이 까다롭고 많았지만 if문을 잘 사용해서 모든 조건을 넣었다.

하지만, 기본적인 bfs로는 시간초과가 계속해서 발생했다.

 

bfs는 최대한 넓게 퍼지면서 확인을 한다.

그래서 한 번에 가는 곳 이후 두 번만에 가는 곳,..., k번 만에 가는 곳.

이 순서대로 탐색을 하니까 시간이 오래 걸릴 것 같았다.

 

그래서 백트래킹이나 dfs처럼 k만큼 길게 탐색한 후 다시 돌아가는 방식을 사용했다.

bfs를 그대로 두고 하고 싶어서 코드를 조금 변경시켰다.

tmp = []
for i in range(4):
    nx = a + dx[i]
    ny = b + dy[i]
    if 0 < nx <= n and 0 < ny <= m and Distance(nx, ny, r, c) + cnt < k:
        tmp.append([nx, ny, cnt + 1, s + dirs[i]])
tmp.reverse()
queue += tmp

원래는 네 방향을 확인해 갈 수 있으면 queue에 넣었다.

그렇게 하면 예를 들어 0 -> 1 1 1 1 -> 1 1 1 2 2 2 2 -> 1 1 2 2 2 2 2 2 2 2 이렇게 될 수 있다.

k번을 확인하기 위해서는 많은 시간이 든다.

 

그래서 tmp에 갈 수 있는 곳을 넣은 후 reverse() 처리해 준다.

그다음에 queue에 붙였다.

while을 반복하면서 빼줄 때는 popleft() 대신 pop()을 이용해 주었다.

이 경우에는 0 -> 1 1 1 1 -> 1 1 1 2 2 2 2가 되더라도 2를 빼주기에 k까지 바로 갈 수 있게 된다.

reverse를 해준 이유는 dirs를 사전순으로 했기 때문에 reverse를 해주었다.

 

dx, dy, dirs를 반대로 설정하고 코드를 돌리면 reverse가 필요 없을 것이다.

혹은 for i in range(3, -1, -1):로 설정해 반대로 해주면 된다.

(코드를 돌려본 결과 이렇게 하더라도 정답이 나온다.)

from collections import deque


def solution(n, m, x, y, r, c, k):
    def Distance(x, y, r, c):
        return abs(r - x) + abs(c - y)

    def bfs():
        queue = deque([])
        queue.append([x, y, 0, ''])
        
        while queue:
            a, b, cnt, s = queue.pop()
            if a == r and b == c:
                if cnt == k:
                    return s
                elif (k - cnt) % 2 == 1:
                    return 'impossible'
            tmp = []
            for i in range(4):
                nx = a + dx[i]
                ny = b + dy[i]
                if 0 < nx <= n and 0 < ny <= m and Distance(nx, ny, r, c) + cnt < k:
                    tmp.append([nx, ny, cnt + 1, s + dirs[i]])
            tmp.reverse()
            queue += tmp
        return 'impossible'
    
    dirs = ['d', 'l', 'r', 'u']
    dx = [1, 0, 0, -1]
    dy = [0, -1, 1, 0]
    
    return bfs()

채점 결과

평소에 bfs()만 주로 해서 dfs()나 백트레킹 같은 경우에는 잘 모르고 있었다.

그래서 이번 문제에서 고생 좀 했다.

 

물론 코딩테스트가 아니라면 bfs()만 알아도 충분할 것 같다.

하지만, 회사의 노예가 되기 위해서라면 다 알아야 할 것 같다.

이번 문제를 통해 많은 것을 배워가는 것 같다.