https://school.programmers.co.kr/learn/courses/30/lessons/150365
문제 설명
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 해야 합니다.
1. 아이디어
사전순의 우선순위는 d, l, r, u 이다.
미로를 탈출하는 경로는 최단경로와 잉여경로로 구분할 수 있고 잉여경로는 u와 d, l과 r의 개수가 동일해야 한다.
전체 경로에서 사전순으로 가장 앞서려면 출발 지점에서 탈출 지점까지 갈 수 있는 선에서 최대한 아래로 먼저 가고 아래로 더 갈 수 없으면 최대한 왼쪽으로 가고 더 왼쪽으로 갈 수 없으면 오른쪽 갔다 왼쪽 갔다를 반복하고 탈출 지점으로 가면 된다.
2. 문제풀이
출발 지점을 기준으로 탈출 지점이 좌하, 우하, 좌상, 우상 4가지 위치 중 어디에 있는지에 따라 조건 분기로 접근했다.
최단 경로와 잉여 경로를 사전순으로 잘 섞는게 중요한데 좌하, 우하는 최단 경로의 아래 방향 커멘드를 먼저하고 잉여 경로의 아래 방향 커멘드를 해준 후 좌우 이동이 끝나면 보정으로 위 방향 커멘드를 해줬다.
좌우 방향 커멘드는 왼쪽 위치면 최단 경로의 왼쪽을 먼저해주고 오른쪽 위치면 잉여 경로의 왼쪽을 먼저 해주는 식으로 접근하면 된다.
아래쪽도 왼쪽도 더 갈 수 없으면 오른쪽으로 한칸 갔다 왼쪽으로 다시 오는게 사전순으로 가장 빨라서 이 부분만 고려해주면 된다.
3. 코드
class Solution {
public String solution(int n, int m, int x, int y, int r, int c, int k) {
// 최단거리가 k보다 길거나 k가 거리경로 + 2의 배수가 아니면 불가능한 케이스
if ((Math.abs(r - x) + Math.abs(c - y)) % 2 != k % 2 || Math.abs(r - x) + Math.abs(c - y) > k) return "impossible";
StringBuilder sb = new StringBuilder();
// 잉여거리
int remain = k - Math.abs(r - x) - Math.abs(c - y);
// 상하 반복 횟수
int udCnt = 0;
// 좌우 반복 횟수
int lrCnt = 0;
if (x < r) {
// 최단 경로에 포함
for (int i = x; i < r; i++) {
sb.append("d");
}
// 잉여 경로에 포함
int dx = r;
while (dx < n && remain > 0) {
udCnt++;
dx++;
remain -= 2;
}
for (int i = 0; i < udCnt; i++) {
sb.append("d");
}
if (y > c) {
// 최단 경로에 포함
for (int i = c; i < y; i++) {
sb.append("l");
}
// 잉여 경로에 포함
int dy = c;
while (dy > 1 && remain > 0) {
lrCnt++;
dy--;
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("l");
}
while (remain > 0) {
sb.append("rl");
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("r");
}
} else {
// 잉여 경로에 포함
int dy = y;
while (dy > 1 && remain > 0) {
lrCnt++;
dy--;
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("l");
}
while (remain > 0) {
sb.append("rl");
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("r");
}
// 최단 경로에 포함
for (int i = y; i < c; i++) {
sb.append("r");
}
}
// 잉여 경로에 포함
for (int i = 0; i < udCnt; i++) {
sb.append("u");
}
} else {
// 잉여 경로에 포함
int dx = x;
while (dx < n && remain > 0) {
udCnt++;
dx++;
remain -= 2;
}
for (int i = 0; i < udCnt; i++) {
sb.append("d");
}
if (y > c) {
// 최단 경로에 포함
for (int i = c; i < y; i++) {
sb.append("l");
}
// 잉여 경로에 포함
int dy = c;
while (dy > 1 && remain > 0) {
lrCnt++;
dy--;
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("l");
}
while (remain > 0) {
sb.append("rl");
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("r");
}
} else {
// 잉여 경로에 포함
int dy = y;
while (dy > 1 && remain > 0) {
lrCnt++;
dy--;
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("l");
}
while (remain > 0) {
sb.append("rl");
remain -= 2;
}
for (int i = 0; i < lrCnt; i++) {
sb.append("r");
}
// 최단 경로에 포함
for (int i = y; i < c; i++) {
sb.append("r");
}
}
// 잉여 경로에 포함
for (int i = 0; i < udCnt; i++) {
sb.append("u");
}
// 최단 경로에 포함
for (int i = r; i < x; i++) {
sb.append("u");
}
}
return sb.toString();
}
}4. 후기
'코딩테스트 준비 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 172927번 - 광물 캐기 [Java] (0) | 2025.03.04 |
|---|---|
| [프로그래머스] 150367번 - 표현 가능한 이진트리 [Java] (0) | 2025.02.22 |
| [프로그래머스] 92342번 - 양궁대회 [Java] (1) | 2025.02.19 |
| [프로그래머스] 130368번 - 이모티콘 할인행사 [Java] (0) | 2025.02.18 |
| [프로그래머스] 12900번 - 2 x n 타일링 [Java] (0) | 2025.02.10 |
