2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150365

파이썬 소스: https://bit.ly/3VXuTIT

 

DFS, BFS 방식으로 2가지 방식으로 모두 풀 수 있는 길찾기 문제의 변형된 형태입니다.

문제를 설명하기에 앞어서, solution()함수의 파라미터를 변경하겠습니다.

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

문제에서 주어진 것은 n, m, x, y 순서입니다. 하지만, 여기서 변수 x는 세로길이를 뜻하기 때문에 아래와 같이 x,와 y를 서로 바꾸도록 하겠습니다.

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

변수 n이 3이라고 할 때, y는 1부터 3까지 가능합니다. 즉, 인덱스가 아닙니다. 따라서, 코딩할 때 익숙한 인덱스로 변경하기 위해서, y, x, r, c 모두 1씩 감소시키겠습니다.

y, x, r, c = y - 1, x - 1, r - 1, c - 1,

여기까지 하면 문제를 풀기위한 준비가 끝났 구요.

 

이 문제를 풀이하는 대 핵심은 최적화를 어떻게 할 것 인가? 입니다. k의 길이가 <= 2500으로 매우 큰 값 이구요, 문제에서 아래와 같이 기술된 것처럼, 중복 방문이 가능하기 때문에, 최적화를 하지 못하면, 몇 개의 테스트 케이스를 제외하고는 모두 시간 초과가 됩니다.

2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.

 

출발지에서부터 탈출지점까지의 최소 거리를 아래와 같이 계산할 수 있습니다.

min_distance = abs(y - r) + abs(x - c)     if  min_distance > k:         return 'impossible'

변수 k값이 이보다 작다면, 탈출지점까지 갈 수 없습니다. Impossible을 리턴합니다.

예를 들어, min_distance가 3인대, k가 4라면, 탈출 지점까지 도착할 수 없습니다. 상/하/좌/우 4방향으로만 이동이 가능하기 때문입니다.

따라서, min_distance가 홀수이면, k도 홀수여야 도착이 가능하고, 그와 반대로 두개의 변수 모두 짝수여야 탈출지점까지 도착할 수 있습니다.

if min_distance % 2 != k % 2:         return 'impossible'

위와 같이 모듈러 2를 해서, 둘 다 짝수 인지 홀수 있지 확인할 수 있습니다.

 

DFS, BFS로 모두 풀이가 가능하지만, 이번에는 DFS를 사용해서 문제를 풀어 보겠습니다.

def dfs(n, m, y, x, dst_y, dst_x, depth, pathes):     if depth == 0:         if y == dst_y and x == dst_x:             return pathes         else:             return None

변수 n, m은 solution() 함수에서 주어진 n, m을 그대로 사용합니다.

변수 dst_y, dst_x 는 r, c값이구요, 변수 이름만 변경한 것입니다.

함수 dfs()가 재귀적으로 호출 되어서, 마지막 까지 왔을 때는 depth가 0이 됩니다.

이 때, y == dst_y 그리고 x == dst_x가 성립하면 탈출지점에 도착할 것으로, 지나온 경로인 pathes를 리턴합니다.

탈출지점에 도착하지 못했으면 None을 리턴하구요.

 

이 문제에서는 탈출한 경로가 사전 순으로 가장 빠른 경로로 탈출해야 한다고 합니다.

따라서, 아래쪽 d를 가장 먼저 방문하고, 그 다음이 왼쪽 l, 그 다음이 오른쪽 r, 마지막으로 u의 순서로 방문해야 합니다. 방문하는 순서가 위와 다르면, 탈출 위치까지 도착하더라도, 경로가 사전순으로 가장 빠르지 않을 수 있기 때문에, 오답을 리턴하게 됩니다.

# d: 아래쪽으로, l: 왼쪽으로, r: 오른쪽으로, u: 위쪽으로     for dy, dx, dir in [[1, 0, 'd'], [0, -1, 'l'], [0, 1, 'r'], [-1, 0, 'u']]:

이제 다음 이동할 위치 ny, nx를 아래와 같이 계산합니다.

ny, nx = y + dy, x + dx if 0 <= ny < n and 0 <= nx < m:

If 문은 n, m을 벗어나지 않는 위치인지 체크 합니다.

 

테스트 케이스의 시간 초과를 피하려면, 여기서 또 한번의 최적화가 필요합니다.

이동할 위치 ny, nx 이동했다고 가정하고, 해당 위치로부터 탈출 지점과의 거리를 계산합니다. 만약 이 거리가, depth – 1 보다 크다면, 도착할 수 없는 거리이기 때문에, dfs()함수를 호출할 필요가 없습니다.

distance = abs(ny - dst_y) + abs(nx - dst_x) if distance > depth -1: continue

 

이동할 위치 ny, nx가 탈출지까지 도착할 수 있는 거리 안에 있으면, dfs()를 호출 합니다.

rtn = dfs(n, m, ny, nx, dst_y, dst_x, depth - 1, pathes + [dir])             if rtn != None:                 return rtn

 

위와 같이 코딩한 전체 코드는 아래와 같습니다.

import sys   sys.setrecursionlimit(10 ** 9) def solution(n, m, y, x, r, c, k):     y, x, r, c = y - 1, x - 1, r - 1, c - 1,     min_distance = abs(y - r) + abs(x - c)     if  min_distance > k:         return 'impossible'     if min_distance % 2 != k % 2:         return 'impossible'     answer = dfs(n, m, y, x, r, c, k, [])     if None == answer:         return 'impossible'     return ''.join(answer) def dfs(n, m, y, x, dst_y, dst_x, depth, pathes):     if depth == 0:         if y == dst_y and x == dst_x:             return pathes         else:             return None     # d: 아래쪽으로, l: 왼쪽으로, r: 오른쪽으로, u: 위쪽으로     for dy, dx, dir in [[1, 0, 'd'], [0, -1, 'l'], [0, 1, 'r'], [-1, 0, 'u']]:         ny, nx = y + dy, x + dx         if 0 <= ny < n and 0 <= nx < m:             distance = abs(ny - dst_y) + abs(nx - dst_x)             if distance > depth -1:                 continue             rtn = dfs(n, m, ny, nx, dst_y, dst_x, depth - 1, pathes + [dir])             if rtn != None:                 return rtn     return None

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul