Programmers에 공개된 2023 KAKAO BLIND RECRUITMENT (2023년 신입 공채 1차 온라인 코딩 테스트) 중에서 Lv.3로 설정되어 있는 미로 탈출 명령어 문제입니다.
1. 문제 및 조건
문제
n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.
격자의 바깥으로는 나갈 수 없습니다.
(x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
l: 왼쪽으로 한 칸 이동
r: 오른쪽으로 한 칸 이동
u: 위쪽으로 한 칸 이동
d: 아래쪽으로 한 칸 이동
예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.
미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.
입력
격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다.
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
출력
미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.
입출력 예시
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" |
2. 설명
움직일 수 있는 횟수가 정해져 있고, 1회 움직일 때 상하좌우 한 번씩 움직일 수 있습니다. 같은 격자를 여러 번 방문해도 상관없다는 조건이 있기 때문에, 지나온 경로 좌표를 따로 저장할 필요는 없습니다. 모든 경우의 수를 다 계산할 경우, k값이 최대 2,500이기 때문에 4의 2,500승이라는 어마어마한 숫자가 나오기 때문에, 모든 경우의 수를 탐색하는 것은 무리가 있어보입니다. 그렇기 때문에 문제의 3번 조건인 사전 순으로 가장 빠른 경로가 중요해 집니다.
사전 순으로 가장 빠른 경로는 1회의 이동에서 사전 순으로 빠른 문자를 선택해서 이동하면 완성되기 때문에, 사전 순으로 빠른 문자를 적절히 선택해서 지정된 횟수로 (x, y)좌표에서 (r, c)좌표까지 도달하게 되면 이후의 탐색은 굳이 탐색할 필요가 없어집니다. 그러므로 (x, y)좌표에서 출발해 (r, c)좌표로 이동하기 때문에, (x, y)좌표를 사전 순으로 빠른 순으로(d > l > r > u) 한 칸씩 이동하면서 k값을 1회씩 소진하고, k = 0이 되는 순간 (x, y) = (r, c)가 되면 탐색을 종료하도록 알고리즘을 구성하면 해결될 것입니다. 여기서 탐색 시간을 줄이기 위해서는 다음의 제약 사항을 추가할 필요가 있습니다.
격자 바깥으로 나갈 수 없다는 규칙이 있으므로, 다음 이동이 격자 바깥으로 나가는 경우 해당 이동을 하는 경우를 고려하지 않습니다.
움직일 수 있는 횟수가 지정되어 있기 때문에 횟수가 0이 될 때 도착 지점에 도착을 할 수 있는지 고려하고, 도착할 수 없는 이동을 하는 경우를 고려하지 않습니다.
1번 조건의 경우, [1 ≤ x ≤ n, 1 ≤ y ≤ m] 조건이 있기 때문에 간단하게 구성할 수 있을 것이라 생각합니다.
2번 조건의 경우, 지정된 횟수로 출발 지점에서 끝 지점까지 도달하는 것은 다음과 같은 규칙이 있습니다.
다음과 같이 (x, y)에서 (r, c) 까지의 거리(최소 이동 횟수)는 |(x - r)| + |(y - c)| = 거리(최소 이동 횟수)라는 식이 완성됩니다. 거리를 구함으로써, k값이 두 가지 조건을 만족해야 돌아올 수 있습니다.
k > 거리를 만족해야 끝 지점에 도달 할 수 있습니다.
1회에 한 칸씩 이동하기 때문에 k - 거리 = 추가 이동 거리(추가 이동 횟수)가 됩니다. 추가 이동 거리의 경우 끝 지점에 되돌아 오기 위해서는 나가는 횟수 1회와 돌아오는 횟수 1회가 필요하기 때문에 반드시 짝수가 되어야 합니다.
3. 해결 방식
return해야 할 문자열의 값을 "impossible"로 초기화 합니다. 이후, 문자열이 "impossible"일 경우에만 탐색을 계속합니다.
1회의 이동을 할 때마다 k를 1씩 감소 시킵니다. (x, y)좌표를 아래(d), 왼쪽(l), 오른쪽(r), 위쪽(u)(사전에서 빠른) 순으로 우선 이동하게 설정합니다. 이동할 때 좌표값 변화는 다음과 같습니다.
아래(d) : (x+1, y)
왼쪽(l) : (x, y-1)
오른쪽(r) : (x, y+1)
위쪽(u) : (x-1, y)
변화할 좌표를 (nx, ny)라고 하고 다음 실행 횟수를 k-1이라고 하면, [1 ≤ nx ≤ n, 1 ≤ ny ≤ m]를 만족할 때 (nx, ny)와 (r, c)사이의 거리를 계산합니다. k-1 < 거리인 경우와 (k-1 - 거리) % 2 != 0인 경우 해당 이동을 무시합니다. 또, return할 문자열이 "impossible"일 경우에만 다음 이동을 실행하도록 코드를 구성하면 해결 됩니다.
4. 코드
public class Solution6 {
private static final String[] dname = {"d", "l", "r", "u"};
private static final int[] dx = {1, 0, 0, -1};
private static final int[] dy = {0, -1, 1, 0};
private static String answer = "impossible";
public static void main(String[] args) {
Solution6 solution6 = new Solution6();
int n = 3;
int m = 4;
int x = 2;
int y = 3;
int r = 3;
int c = 1;
int k = 5;
System.out.println(solution6.solution(n, m, x, y, r, c, k));
}
public String solution(int n, int m, int x, int y, int r, int c, int k) {
if(k < getDistance(x, y, r, c) || ((k - getDistance(x, y, r, c)) % 2 != 0)) return answer;
move(n, m, x, y, r, c, k, "");
return answer;
}
private void move(int n, int m, int x, int y, int r, int c, int k, String log){
if(k == 0){
if(x == r && y == c){
answer = log;
}
return;
}
for(int i=0;i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 0 && nx <= n && ny > 0 && ny <= m){
if(k-1 < getDistance(nx, ny, r, c) || ((k-1 - getDistance(nx, ny, r, c)) % 2 != 0)) continue;
if(answer.equals("impossible")) move(n, m, nx, ny, r, c, k-1, log+dname[i]);
else return;
}
}
}
private int getDistance(int x, int y, int r, int c){
return Math.abs(x - r) + Math.abs(y - c);
}
}
Write one-day, one-blog for MZ generation.
テトリスプログラムを開発してみましょう。