99클럽 코테 스터디 7일차 TIL
[level 3] 미로 탈출 명령어 - 150365
성능 요약
메모리: 10.3 MB, 시간: 0.00 ms
구분
코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2024년 04월 17일 21:59:46
문제 설명
n
x m
격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.
- 격자의 바깥으로는 나갈 수 없습니다.
- (x, y)에서 (r, c)까지 이동하는 거리가 총
k
여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. - 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
- l: 왼쪽으로 한 칸 이동
- r: 오른쪽으로 한 칸 이동
- u: 위쪽으로 한 칸 이동
- d: 아래쪽으로 한 칸 이동
예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"
로 나타낼 수 있습니다.
미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.
예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.
....
..S.
E...
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .
은 빈 공간, S
는 출발 지점, E
는 탈출 지점입니다.
탈출까지 이동해야 하는 거리 k
가 5라면 다음과 같은 경로로 탈출할 수 있습니다.
- lldud
- ulldd
- rdlll
- dllrl
- dllud
- ...
이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.
격자의 크기를 뜻하는 정수 n
, m
, 출발 위치를 뜻하는 정수 x
, y
, 탈출 지점을 뜻하는 정수 r
, c
, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k
가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"
을 return 해야 합니다.
제한사항
- 2 ≤
n
(= 미로의 세로 길이) ≤ 50 - 2 ≤
m
(= 미로의 가로 길이) ≤ 50 - 1 ≤
x
≤n
- 1 ≤
y
≤m
- 1 ≤
r
≤n
- 1 ≤
c
≤m
- (
x
,y
) ≠ (r
,c
) - 1 ≤
k
≤ 2,500
입출력 예
n | m | x | y | r | c | k | result |
---|---|---|---|---|---|---|---|
3 | 4 | 2 | 3 | 3 | 1 | 5 | "dllrl" |
2 | 2 | 1 | 1 | 2 | 2 | 2 | "dr" |
3 | 3 | 1 | 2 | 3 | 3 | 4 | "impossible" |
입출력 예 설명
입출력 예 #1
문제 예시와 동일합니다.
입출력 예 #2
미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.
빈 공간은 .
, 출발 지점을 S
, 탈출 지점을 E
로 나타내면 다음과 같습니다.
S.
.E
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.
탈출까지 이동해야 하는 거리 k
가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.
- rd
- dr
"dr"
이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"
을 return 해야 합니다.
입출력 예 #3
미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.
빈 공간은 .
, 출발 지점을 S
, 탈출 지점을 E
로 나타내면 다음과 같습니다.
.S.
...
..E
미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.
탈출까지 이동해야 하는 거리 k
가 4입니다. 이때, 이동 거리가 4이면서, S
에서 E
까지 이동할 수 있는 경로는 존재하지 않습니다.
따라서 "impossible"
을 return 해야 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
풀이 - DFS
import sys
sys.setrecursionlimit(10**8)
# down, left, right, up 알파벳 순으로 정렬
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
dAlpha = ['d', 'l', 'r', 'u']
answer = "z" # 가능한 경로중 사전 순으로 가장 앞서는 경로를 저장. 초기값 z으로 설정하여 모든 문자열보다 뒤에 오도록 함
# isValid 함수는 주어진 위치가 n*m 격자 안에 있는지 확인
def isValid(nx, ny, n, m) :
return 1 <= nx <= n and 1 <= ny <= m
# dfs함수는 깊이 우선 탐색을 통해 가능한 모든 경로를 찾는다.
def dfs(n, m, x, y, r, c, prev_s, cnt, k) :
global answer
# 현재 위치에서 목표 위치까지의 최소 이동 횟수보다 남은 이동 가능 횟수가 적을 경우 탐색 종료
if k < cnt + abs(x - r) + abs(y - c) :
return
# 목표 위치에 도달했고 이동 횟수가 정확히 k일 때, 경로를 업데이트
if x == r and y == c and cnt == k :
answer = prev_s
return
# down, left, right, up 이동시도
for i in range(4) :
# 다음 위치가 유효하고 현재 경로가 지금까지의 최적해보다 사전순으로 앞서면 탐색 계속
if isValid(x+dx[i], y+dy[i], n, m) and prev_s < answer :
dfs(n, m, x+dx[i], y+dy[i], r, c, prev_s + dAlpha[i], cnt + 1, k)
def solution(n, m, x, y, r, c, k):
# 맨해튼 거리 계산
distance = abs(x - r) + abs(y - c)
# 맨해튼 거리가 k보다 크거나, k와 거리의 차이가 홀수일 경우, 도착할 수 없으므로
if distance > k or (k - distance) % 2 == 1 :
return "impossible"
dfs(n, m, x, y, r, c, "", 0, k)
return answer
풀이 - 수학
def solution(n, m, x, y, r, c, k):
diff = abs(x - r) + abs(y - c)
# 목표까지의 거리가 k와 같은 홀수/짝수여야 하며, k가 더 커야 함
if diff % 2 != k % 2 or diff > k :
return "impossible"
rest = k - diff # 남은 이동 횟수
lcnt = rcnt = dcnt = ucnt = 0
# x, y에서 r, c까지의 기본적인 이동 횟수 계산
if x < r :
dcnt = r - x
else :
ucnt = x - r
if y < c :
rcnt = c - y
else :
lcnt = y - c
# 남은 이동 횟수를 최대한 활용해서 추가적인 이동 횟수를 계산
dplus = min(n - max(x, r), rest // 2)
rest -= dplus * 2
lplus = min(min(y, c) - 1, rest // 2)
rest -= lplus * 2
# 최종 경로 문자열 생성
answer = 'd'*(dcnt + dplus)+'l'*(lcnt + lplus)+'rl'* (rest//2)+'r'*(rcnt+lplus)+'u'*(dplus+ucnt)
return answer
조건을 잘 살펴보면,
시작점 (x, y) 로부터 목표점(r,c)까지 정확히 k번 이동하여 도달할 수 있는 경로 중 사전순으로 가장 앞서는 경로를 찾는 문제
- dx, dy, dAlpha 배열은 상하좌우 이동을 위한 배열이며, 각각 상 하 좌 우 이동을 나타낸다. dAlpha는 이동 방향을 문자로 나타내는 배열로, 이 배열의 값들은 최종 경로 문자열을 구성하는데 사용된다.
- isValid 함수는 주어진 위치가 n * m 배열 안에 있는지 확인하는 함수다. 이동 가능성을 검사할 때 사용된다.
- dfs 깊이 우선 탐색 함수. 현재 위치에서 목표 위치까지 도달할 수 있는지, 그리고 이동 횟수가 정확히 k인지 검사한다. 조건을 만족하면 answer를 업데이트 한다. 이 함수는 모든 상하좌우 방향으로 재귀적으로 자신을 호출하며, 가능한 모든 경로를 탐색한다.
- solution : 시작점에서 목표점까지의 맨해튼 거리를 계산하고, 이 거리가 k보다 크거나 k와 거리의 차이가 홀수일 경우 "impossible"을 반환한다. 그렇지 않을 경우, dfs함수를 호출하여 가능한 경로를 탐색하고, 최적의 경로를 반환한다.
- 맨해튼 거리를 이용한 필터링 : 시작점에서 목표점까지의 맨해튼 거리가 k보다 크거나, k와 거리의 차이가 홀수인 경우, 문제의 조건을 만족하는 경로는 존재할 수 없다. 이는 최소 이동 횟수를 만족하지 않거나, 홀/짝수 이동 횟수의 불일치 때문이다
- DFS : 가능한 모든 경로를 탐색하여 조건을 만족하는 최적의 경로를 찾아낸다. 재귀적으로 모든 방향을 탐색하며, 유효한 이동만을 수행한다. 탐색 과정에서 사전 순으로 더 앞서는 경로를 발견할 경우, answer를 업데이트한다.
챌린저 문제를 해결하면서 구현 시뮬레이션 등을 많이 연습해오고 있지만, 아직까지 많은 어려움이 있다. 그리고 아이디어를 떠올리는데 있어 많은 시행착오가 필요하다고 생각한다.