문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/150365
[2023 KAKAO BLIND RECRUITMENT]에 나왔던 문제.
카카오의 최신 출제 트렌드를 파악하지 못한 나의 잘못이 컸다.
그걸 알았다면 처음에 잘못 접근하지 않아서 시간을 잡아먹지 않았을 것이다..
지금 생각해 보면 당연한 건데, 왜 헛다리 짚었을까?
문제 핵심 및 풀이
핵심 파악
이 문제에서 핵심은 도착점까지 가장 빠른 경로를 찾는 것이 아니라, 무조건 k 횟수를 움직여야 한다는 점이다.
가장 빨라야 하는 것은 경로가 아닌 움직인 경로의 문자열 사전순이다.
상하좌우를 각각 'u' , 'd' , 'l' , 'r'로 나타낸다.
각 방향마다 문자가 정해져 있다는 것은, 움직이는 방향의 우선순위가 존재한다는 것이다.
이게 무슨 소리일까?
만약 k = 3이기 때문에 3번 움직여야 한다고 생각해 보자.
"uuu", "ddd", "udl", "rlr"... 등등 엄청나게 많은 경우의 수가 나올 수 있다.'
여기서 사전순으로 빠르다는 것은, 알파벳 순서가 빠른 것 앞에 많다는 것을 의미한다.
(ddd > ddl > ddr > ddu > dld > dlr... >... > uuu)
즉, 상하좌우에서 나올 수 있는 알파벳 'u' , 'd' , 'l' , 'r'은
d > l > r > u(하 > 좌 > 우 > 상) 순서로 우선순위를 갖는다.
예제를 통해 가장 처음 움직일 때를 가정
입출력 예 1번으로 한번 해보자.
해당 문제에서는 k = 5이기 때문에, 5번을 무조건 움직여야 한다.
첫 번째 움직일 때를 고려해 보자. 최종적으로 X???? 가 되는 부분이다.
이 자리 뒤에 알파벳이 아무리 빨라도 이 자리가 느리면 사전 순으로 느린 게 된다.
예를 들어서, ldddd보다 duuuu가 사전순으로 더 빠르듯이 말이다.
근데 우리는 1번째 움직임만으로는 해당 방향으로 간 것이
k 번만에 도착지까지 갈 수 있을지 알 수 없다.
결국 k번 전부 움직여봐야지만 성공/실패 결과를 알 수 있다.
이건 비단 1번째 움직임뿐만 아니라, 2번째 움직임, 3번째 움직임에서도 마찬가지이다.
이 문제를 어떻게 해결해야 할까?
여기서 우리는 DFS와 위에서 찾았던 핵심을 섞어서 해결하면 된다.
최선의 우선순위로 움직이기
k = 5 일 때, 도착지에 상관없이 사전순으로 가장 빠르게 움직인다고 하면? 당연히 "ddddd"이다.
이 결론은 어떻게 나왔는가? 하 > 좌 > 우 > 상 ( d > l > r > u )의 우선순위를 근거로 하여 나왔을 것이다.
그렇다면 "ddddd"가 불가능하다고 하면?
우리는 그다음 사전순으로 빠른 "ddddl"을 뽑을 것이다.
이렇게 1순위가 안되면 2순위를 해보고, 안되면 3순위, 4순위를 해보는 식이다.
한마디로 각 자리에서 먼저 아래로 움직이고, 안되면 그다음은 왼쪽으로 움직여보고,
다음은 오른쪽, 마지막으로 위로 움직이는 것이다.
이를 DFS와 섞어서 하, 좌, 우, 상 순으로 계속 움직이게 한다면 답을 쉽게 구할 수 있다.
말로 하면 잘 이해가 안 갈 수도 있으니까 입출력 예 1번으로 시뮬레이션을 돌려보자.
예제 1을 통한 시뮬레이션
1번째에는 우선순위가 가장 빠른 아래(d)로 이동이 가능하므로 이동한다.
하지만 2번째에는 아래(d)로 이동하는 것이 불가능하다.
그래서 그다음 우선순위인 왼쪽(l)으로 움직인다.
3번째에도 아래(d)로 움직일 수 없으니 왼쪽으로 이동한다.
도착지(E)에 도달했지만 아직 이동 횟수가 다 소모가 안 됐으므로 계속한다.
4번째에는 아래(d)와 왼쪽(l) 둘 다 움직일 수 없기 때문에, 3번째 우선순위인 오른쪽(r)으로 움직인다.
k = 0, 즉 이동 횟수를 다 소모했을 때, 도착점에 도달했다.
또한 도착점에 도달할 수 있는 경로 중,
가장 사전 순으로 빠르게 움직였기 때문에 해당 경로가 답이 된다.
근데 이게 왜 DFS로 해야 하는 걸까?
이걸 DFS로 하면 최적화되는 이유는 방문 처리에 있다.
여기서 k = 3이고, 맵의 크기가 아래와 같은 경우를 생각해 보자.
위의 논리대로라면 k = 3 일 될 때 "ddl"이 될 것이다.
k = 3 일 때, 위의 논리대로라면 ddl이 되겠지만,
이렇게 되면 도착점에 도달하지 못하게 때문에 가능하지 않은 경로이다.
즉 다른 경로를 구해야 한다.
하지만 이 "dd" 일 때는 어느 경로로도 가능하지 않다.
즉, 애초에 아래(d)로 내려오는 것 자체가 틀렸다는 것 뜻한다.
그러니까 k = 3을 호출한 함수가 잘못되었음을 의미하므로,
그 함수로 돌아가 d 말고 다른 자리를 찾아야 한다.
같은 원리로 최종 답을 구할 수 있게 된다.
또한 남은 각 칸별로 k 횟수별로 방문 횟수를 기록해 두면, 재방문을 방지할 수 있다.
이 칸은 이미 방문했기 때문에 다른 방향에서는 방문이 불가능하기 때문에,
추후 불필요한 재귀함수 호출을 막을 수 있다.
이런 식으로 DFS를 전개하면 답을 구할 수 있다.
나머지 자세한 것은 코드 구현 부분에서 주석으로 보면 이해가 될 것이다.
실수하기 쉬운 부분
방문 배열을 만들어줄 때, k에 횟수에 다르게 담아둘 수 있도록 3차원을 만들어야 한다.
또한 방문을 한 뒤 DFS 이후, 방문을 풀어주면 안 된다.
그러면 불필요한 재귀함수를 또 하게 돼서 시간초과가 뜬다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 순서롤 무조건 (하,좌,우,상) 해야함
int dx[] = {1,0,0,-1};
int dy[] = {0,-1,1,0};
// 각 인덱스에 맞는 문자 매핑
char dir[] = {'d','l','r','u'};
// 3차원으로 방문 배열을 만들어줘야함
bool visited[51][51][2501];
// 정답 경로
string result = "";
// 도착지 전역변수화
int endX;
int endY;
// 맵의 크기
int nn;
int mm;
// 정답이 구해졌으면 더이상 DFS를 못하도록 하기 위한 플래그
bool finish = false;
void dfs(int x, int y, int k, string cnt){
if(finish) return; // 정답이 구해졌으면 더이상 안함
// k = 0 일때 해당 자리가 도착 지점이면 성공한 것
if(k == 0){
if(x == endX && y == endY){
finish = true;
result = cnt;
}
return;
}
// 인덱스를 0 ~ 3으로 호출함으로써 우선순위대로 호출
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// k-1은 이동 이후의 남은 횟수를 뜻함
if(nx > nn || ny > mm || nx < 1 || ny < 1 || visited[nx][ny][k-1]) continue;
// 방문 체크
visited[nx][ny][k-1] = true;
// 재귀호출
dfs(nx,ny,k-1,cnt + dir[i]);
if(finish) return;
}
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
string answer = "";
nn = n;
mm = m;
endX = r;
endY = c;
dfs(x,y,k,"");
answer = (result.empty())?"impossible" : result;
return answer;
}
Java 구현 코드
↓
import java.util.*;
class Solution {
// 순서롤 무조건 (하,좌,우,상) 해야함
int[] dx = {1,0,0,-1};
int[] dy = {0,-1,1,0};
// 각 인덱스에 맞는 문자 매핑
String[] dir = {"d","l","r","u"};
// 도착지 전역변수화
int endX;
int endY;
// 맵의 크기
int n,m;
// 3차원으로 방문 배열을 만들어줘야함
boolean[][][] visited = new boolean[51][51][2501];
// 정답이 구해졌으면 더이상 DFS를 못하도록 하기 위한 플래그
boolean finish = false;
// 일단 숫자로 받은 다음 문자로 전환할 것임
List<Integer> result;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer = "";
this.n = n;
this.m = m;
endX = r;
endY = c;
dfs(x,y,k,new ArrayList<>());
StringBuilder sb = new StringBuilder();
if(result == null) answer = "impossible";
else {
for(int i : result){
sb.append(dir[i]);
}
answer = sb.toString();
}
return answer;
}
void dfs(int x, int y, int k, List<Integer> cnt){
if(finish) return; // 정답이 구해졌으면 더이상 안함
// k = 0 일때 해당 자리가 도착 지점이면 성공한 것
if(k <= 0){
if(x == endX && y == endY) {
result = cnt;
finish = true;
}
return;
}
// 인덱스를 0 ~ 3으로 호출함으로써 우선순위대로 호출
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// k-1은 이동 이후의 남은 횟수를 뜻함
if(nx > n || ny > m || nx < 1 || ny < 1 || visited[nx][ny][k-1]) continue;
// 방문 체크
visited[nx][ny][k-1] = true;
List<Integer> list = new ArrayList<Integer>(cnt);
list.add(i);
dfs(nx,ny,k-1,list);
if(finish) return;
}
}
}
시행착오
처음엔 dfs로 하면 시간초과가 뜰 줄 알고, 어떻게든 DP로 풀어보려고 했다.
그러다 보니 계속 틀렸고, 생각해 보니 DFS로도 충분히 풀 수 있는 문제였다.
생각해 보면 요즘 카카오 DP 문제 잘 안 내는데, 왜 DP라고 생각했을까?
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me