문제

풀이

• 처음 BFS로 했다가 시간 초과 발생
• DFS로 d l r u 사전 순으로 먼저 이동
• 테스트케이스 31번에서 시간 초과 발생
  • k보다 거리가 짧으면 왔다갔다를 해야돼서 짝수로 떨어져야함

//조건 추가해줘서 해결
int distance=k-(Math.abs(r-x)+Math.abs(c-y));
if(distance<0||distance%2!=0)return "impossible";

---

코드

import java.util.*;
class Solution {
        static int[][] board;
        static final int[][] d=new int[][]{{1,0},{0,-1},{0,1},{-1,0}};
        static String answer;
        static int n,m,k;
        static boolean flag;
        public String solution(int n, int m, int x, int y, int r, int c, int k) {
            answer = "";
            this.n=n;
            this.m=m;
            this.k=k;
            flag=false;
            board=new int[n+1][m+1];
            int distance=k-(Math.abs(r-x)+Math.abs(c-y));
            if(distance<0||distance%2!=0)return "impossible";
            else {
                dfs(x,y,r,c,0,"");
            }
            if(!flag)answer="impossible";
            return answer;
        }

        static void dfs(int y,int x,int r,int c,int depth,String cmd){
            if(flag)return;
            if(depth==k){
                if(y==r&&x==c){
                    flag=true;
                    answer=cmd;
                }
                return;
            }
            int distance=Math.abs(r-y)+Math.abs(c-x);
            if(k-depth<distance)return;
            for(int i=0;i<4;i++){
                if(flag)return;
                int dy=y+d[i][0];
                int dx=x+d[i][1];
                if(dy<1||dx<1||dy>n||dx>m)continue;
                String newCmd=cmd;
                if(i==0)newCmd+="d";
                else if(i==1)newCmd+="l";
                else if(i==2)newCmd+="r";
                else newCmd+="u";
                dfs(dy,dx,r,c,depth+1,newCmd);
            }
        }
}

#dfs