https://school.programmers.co.kr/learn/courses/30/lessons/150365
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
<풀이>
1. 미로 정보를 입력받는다.
2. 사전 순으로 가장 빠른 미로 탈출 경로를 반환한다.
<해법>
1. 완전탐색 X
=> 평범한 길찾기 문제라는 생각이 듭니다. 하지만 이 문제는 k가 최대 2500이므로, 완전탐색으로 풀 때 최악의 경우 O(4^2500)의 시간복잡도를 가집니다. 따라서, 완전탐색 알고리즘은 배제해야합니다.
2. 불가능한 경우 찾기
=> 먼저 "impossible"한 경우부터 생각해보겠습니다.
첫번째로, 출발지점에서 끝지점까지 갈 수 있는 최단거리보다 k가 작을 경우 불가능합니다. 여기서, 출발지점에서 끝지점까지 최단거리를 계산하는 방법은 매우 간단합니다. 지도 상에 장애물이 없으므로, 맨해튼 거리계산법(ㅣx - rㅣ+ ㅣy - cㅣ)를 이용해서 구할 수 있습니다. 따라서, if(최단거리 > k) answer = "impossible" 입니다.
두번째로, (k - 최단거리) % 2 == 1 일 때 불가능합니다. 이유는 k번을 채우기 위해서는 어디선가 왔다갔다를 해야하기 때문입니다. 단순히 k번을 이용한 거리를 구하라고 한다면, 출발지점에서 끝지점까지 간 후 끝지점에서 바로 옆칸으로 왔다갔다하면 구할 수 있습니다. 그런데 이 때, '왔다갔다'를 해야하므로 2번이 필요합니다. 만약 도착지점에서 k가 1이라면 불가능합니다. 따라서, if((k - 최단거리) % 2 == 1) answer = "impossible" 입니다.
3. 사전순으로 가장 빠른 경로 찾기
=> 위 경우를 제외하고서는 k번 이동하여 출발지점부터 끝지점까지 갈 수 있습니다. 이제 사전순으로 가장 빠른 경로를 찾아야합니다. 사전순으로 가장 빠르려면, 앞자리가 가장 빨라야합니다. 이 말은 'd(아래)로 갈 수 있으면, d로 가는게 가장 좋다.' 입니다. 또, 'd -> l -> r -> u 순으로 갈 수있는 곳을 탐색해서 간다.' 가 됩니다.
그렇다면 이제 해당 방향으로 가도 되는지 안되는지 판단하는 일만 남았습니다. 해당 방향으로 가도 되려면, 먼저 맵을 벗어나면 안됩니다. 그리고 또 한가지는 위에 "impossible"한 경우가 아니면 됩니다. 이 말은 다음 위치에서 최단거리 <= 남은 k 면 된다는 뜻입니다. 이렇게 하면 greedy하게 사전순으로 가장 빠른 방향으로 이동하며 정답을 구할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <string>
#include <vector>
using namespace std;
char d[] = { 'd', 'l', 'r', 'u' };
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,-1,1,0 };
bool isInner(int x, int y, int n, int m) {
if (x <= 0 || y <= 0 || x > n || y > m) return false;
return true;
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
string answer = "";
int shortest = abs(x - r) + abs(y - c);
if (shortest > k || (k - shortest) % 2) answer = "impossible";
else {
while (k--) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (!isInner(nx, ny, n, m)) continue;
int nshortest = abs(nx - r) + abs(ny - c);
if (nshortest > k) continue;
x = nx, y = ny;
answer += d[i];
break;
}
}
}
return answer;
}
|
Greedy 알고리즘에 대해 알아볼 수 있었습니다.
'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글
| [C++] 프로그래머스 - 표 병합 (0) | 2023.02.02 |
|---|---|
| [C++] 프로그래머스 - 표현 가능한 이진트리 (0) | 2023.02.02 |
| [C++] 프로그래머스 - 이모티콘 할인행사 (0) | 2023.02.01 |
| [C++] 프로그래머스 - 택배 배달과 수거하기 (0) | 2023.02.01 |
| [C++] 프로그래머스 - 개인정보 수집 유효기간 (0) | 2023.02.01 |
