https://school.programmers.co.kr/learn/courses/30/lessons/150365
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🌿 - 문제 설명
📌- 풀이
문제를 보고 처음에는 BFS로 {d, l , r , u} 의 순서대로 완전탐색을 하면 되겠구나 생각해서 그렇게 문제를 풀려고 했는데, 전부 다 탐색을 하게 되면 분명 시간 초과가 날 것 같다고 생각해서 다른 방식을 생각해보게 되었다.
일단 주어진 문제에서 문자열을 사전순서대로 가장 빠른 순이라고 했기 때문에 dlru순으로 탐색을 하긴 하는데, 이것을 DFS로 탐색을 하게되면 K의 수 만큼 -> 예를들어 k가 5라면
ddddd부터 시작해서 ddddl -> ddddr -> 이렇게 탐색하게 되고 가장 먼저 k == 0 이고 목적지에 도착한 문자열이 정답이 되기 때문에 그렇게 구현을 했다. 처음 풀었을 때 시간 초과가 났고, 어떻게 가지치기를 해야할지 고민을 해서 개선을 했다.
🔥 - 처음 시간 초과 난 코드
class Solution {
static int[] dx = {1,0,0,-1};
static int[] dy = {0,-1,1,0};
static String[] direction = {"d","l","r","u"};
static String result ="";
static int N,M;
static boolean fin = false;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer = "";
N = n;
M = m;
dfs(x-1,y-1,r-1,c-1, k, "");
answer = result.equals("") ? "impossible" : result;
return answer;
}
public void dfs(int startX, int startY,int endX,int endY, int k , String str){
if(k==0 && startX == endX && startY == endY){
result = str;
fin = true;
return;
}
if(k==0 || fin){
return;
}
for(int i =0;i<4;i++){
int nx = startX + dx[i];
int ny = startY + dy[i];
if(0<= nx && nx<N && 0<= ny && ny<M){
dfs(nx,ny,endX,endY, k-1, str+direction[i]);
}
}
}
}
위의 방식대로 하면 정답이 나오지 않더라도 탐색을 하는 경우가 많기 때문에
아래처럼 현재 위치한 곳과 도착지점의 거리를 구해서 해당 수가 k와 짝수인지 홀수인지 비교해서 짝/홀수가 같다면 탐색할 수 있고, 짝 홀수가 다르다면 갈 수 없는 곳이라 탐색할 필요가 없기 때문에 해당 조건으로 가지치기를 해서 시간초과를 해결했다.
🔥 - 개선한 코드
class Solution {
static int[] dx = {1,0,0,-1};
static int[] dy = {0,-1,1,0};
static String[] direction = {"d","l","r","u"};
static String result ="";
static int N,M;
static boolean fin = false;
public String solution(int n, int m, int x, int y, int r, int c, int k) {
String answer = "";
N = n;
M = m;
int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
dfs(x-1,y-1,r-1,c-1, k, "",diff);
answer = result.equals("") ? "impossible" : result;
return answer;
}
public void dfs(int startX, int startY,int endX,int endY, int k , String str, int diff){
if(k==0 && startX == endX && startY == endY){
result = str;
fin = true;
return;
}
if(k==0 || fin){
return;
}
for(int i =0;i<4;i++){
int nx = startX + dx[i];
int ny = startY + dy[i];
if(0<= nx && nx<N && 0<= ny && ny<M && diff <=k){
if((diff % 2 == 0 && k % 2 == 0) || (diff %2 == 1 && k %2 == 1)){
dfs(nx,ny,endX,endY, k-1, str+direction[i],Math.abs(nx-endX) + Math.abs(ny-endY));
}
}
}
}
}