성능 요약
메모리: 87.6 MB, 시간: 1.52 ms
구분
코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2025년 02월 20일 17:17: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
풀이
느낀점
- 처음엔 bfs인가 했는데 백트래킹을 하다보니 bfs이든 dfs이든 한번에 끝나서 좀 더 간단한 방법이 있지 않을까 싶었다.
- bfs로 풀었을때 몇몇 테케가 런타임에러가 나서, 재귀함수 형식으로 수정했더니 해결됐다.. 왜그랬던 걸까
- 예상하기로는 Queue를 사용할때 NullPointException이 뜨는 예외가 있지 않았을까 싶다.
설계 : 15분
- 각 칸에서 탈출로까지의 최소거리를 배열에 저장해둔다.
- 격자를 넘어가면 안되기 때문에 배열은 가장자리 한칸씩 패딩 처리해서 MAX값으로 채운다.
- 시작점부터 순회한다.
- 사방탐색 순서는 문자의 사전순에 따라 하, 좌, 우, 상 으로 한다.
- 순서대로 탐색하면서 이동 가능한 방향을 찾으면 같은 depth에서는 더이상 탐색하지 않는다. (사전순으로 먼저여야 하기 때문에 구해졌으면 끝)
- 이동이 가능하다는 조건은? 이동할 칸에서의 탈출로 도달 가능 여부를 체크한다.
- 이동하려는 칸에서
탈출로까지의 최단거리 > 남은 이동 가능 횟수이면 도달 불가능 - 이동하려는 칸에서 탈출로까지의 최단거리와 남은 이동 횟수의 홀짝 여부가 동일하지 않으면 도달 불가능(경로를 돌아가더라도 최단경로가 짝수이면 짝수번으로만 도달할 수 있다)
- MAX값과의 비교를 통해 격자 바깥으로의 이동 차단
- 이동하려는 칸에서
코드(Java)
- 구현 시간: 90분
import java.util.*;
import java.lang.*;
class Solution {
static final int MAX = 3_000;
static int[] dr = {1, 0, 0, -1};
static int[] dc = {0, -1, 1, 0};
static char[] dChar = {'d', 'l', 'r', 'u'};
static int[][] dist;
static char[] answer;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
answer = new char[k];
// 각 칸에서 탈출로까지의 최단거리, 격자 바깥은 MAX
dist = new int[n+2][m+2];
Arrays.fill(dist[0], MAX);
Arrays.fill(dist[n+1], MAX);
for (int i = 1; i <= n; i++) {
dist[i][0] = dist[i][m+1] = MAX;
for (int j = 1; j <= m; j++) dist[i][j] = Math.abs(i-r) + Math.abs(j-c);
}
answer = new char[k];
move(x, y, k, 0);
if (answer[k-1] == '\u0000') return "impossible";
return String.valueOf(answer);
}
public static void move(int r, int c, int rest, int idx) {
if (rest <= 0) return;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (dist[nr][nc] == MAX || dist[nr][nc] > rest-1
|| (rest-1-dist[nr][nc]) % 2 != 0) continue;
answer[idx] = dChar[d];
move(nr, nc, rest - 1, idx + 1);
break;
}
}
}