문제
코드
import java.util.*;
class Solution {
int Rsize,Csize,Rgoal,Cgoal,count;
boolean find=false;
String answer="impossible";
public String solution(int n, int m, int x, int y, int r, int c, int k) {
Rsize=n;
Csize=m;
Rgoal=r-1;
Cgoal=c-1;
count=k;
dfs(x-1,y-1,"");
return answer;
}
public void dfs(int r,int c,String str){
if(find) return;
int distance=Math.abs(r-Rgoal)+Math.abs(c-Cgoal);
if(distance>count-str.length()||(count-str.length()-distance)%2!=0) return;
if(str.length()==count){
find=true;
if(r==Rgoal&&c==Cgoal) answer=str;
return;
}
if(r<Rsize-1){
String newStr=str+"d";
dfs(r+1,c,newStr);
}
if(c>0){
String newStr=str+"l";
dfs(r,c-1,newStr);
}
if(c<Csize-1){
String newStr=str+"r";
dfs(r,c+1,newStr);
}
if(r>0){
String newStr=str+"u";
dfs(r-1,c,newStr);
}
}
}풀이
최적화가 필요한 dfs문제이다. 그냥 dfs로만 풀면 시간초과가 난다.
일단 이 문제는 찾은 답 중에서 사전 순으로 가장 빠른 답을 구하는 문제이다.
하지만, 모든 답을 찾고 정렬을 해버리면 시간초과가 난다.
그래서 탐색 자체를 d(하)-l(좌)-r(우)-u(상) 순서대로 하면, 가장 먼저 도착한 답이 사전 상 가장 빠른 문자열이 되므로 정답이 된다.
(1) 먼저, 시작 지점으로부터 dfs탐색을 시작한다.
(2) dfs 함수에서는 다음을 실행한다.
- 이미 정답을 찾았으면(find==true, 가장 먼저 도착한 답이 정답이기 때문에), 탐색을 종료한다.
- 현재 위치와 탈출 위치의 거리를 구해준다.(distance)
- 만약, 거리가 남은 이동 횟수보다 크면 탐색을 종료한다.(남은 이동횟수 내로 탈출구까지 이동할 수 없기 때문)
- 만약, 남은 이동횟수-거리가 홀수이면 탐색을 종료한다.(짝수이면 같은곳을 왔다갔다 거리면서 탈출구에 도착할 수 있는데, 홀수이면 남은 이동횟수로 도착할 수 없다.)
- 이동횟수(k)만큼 이동했고, 현재 위치가 탈출 위치이면 answer에 탐색한 문자열, find를 true로 초기화하고 탐색을 종료한다.
- 위의 탐색 종료 조건을 통과한다면, d-l-r-u 순으로 다음 탐색 위치를 찾아 dfs()를 재귀호출 한다.
(3) 가장 먼저 찾은 답이 정답이므로, 한번 답을 찾으면 다른 탐색들은 find=true가 되어 종료된다. 그렇기 때문에, 그냥 answer을 return 해주면 된다.
결과
처음엔 그냥 dfs 탐색으로 풀면 되겠다 싶어서 풀었더니, 시간초과가 났다.
그리고 어떻게 탐색 횟수를 줄여야 할 지 도저히 생각이 안나서 다른사람 풀이를 참고했다.
거리와 남은 이동횟수를 계산한 후, 도달할 수 없는 경우들을 가지치기 했는데도 또다시 시간초과가 났다.
모든 답을 찾는 방식이 문제였다.
모든 답을 찾아 사전 순으로 정렬하는 것이 아닌 사전 순으로 탐색을 해서 가장 먼저 찾은 답을 정답으로 하는 방식을 사용해야 했다.
풀만 한 것 같으면서도 어려운 문제였다. 사전 순으로 상하좌우를 탐색한다는 생각을 하기가 어려웠다.
카카오 문제라 그런지 퀄리티가 좋은듯 하다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges
