🔎 문제 설명

문제
https://school.programmers.co.kr/learn/courses/30/lessons/150365
정답
https://github.com/ji-yeon224/coding-test/blob/master/programmers/%EB%AF%B8%EB%A1%9C_%ED%83%88%EC%B6%9C_%EB%AA%85%EB%A0%B9%EC%96%B4/Solution.java

💡 풀이 방식

✔ impossible인 경우

int length = distance(x, y, r, c);
if((k - length) % 2 == 1 || k < length) return "impossible";

1. 목표 거리(k) - (시작 점에서 부터 목표지점 까지 최단 거리) 가 짝수여야 함

• k와 최단 거리가 둘 다 짝수이거나 둘 다 홀수여야 가능하다.
• 그림 그려서 계산하면 알 수 있다.
  
  

2. k가 최단 거리보다 짧을 경우 불가능

✔ dfs 탐색

• dfs를 이용하여 백트래킹 방식으로 구현
• 사전 순으로 d -> l -> r -> u 순서로 탐색함
  • 사전 순으로 탐색하기 때문에 최종 결과물은 사전 순 가장 앞에 있는 결과 값이 나온다.

char[] dir = {'d', 'l', 'r', 'u'};
int[] rdir = {1, 0, 0, -1};
int[] cdir = {0, -1, 1, 0};

• dfs로 탐색하면서 루트 탐색
• 현재 깊이와 현 위치에서 목적 지점까지의 최단 거리의 합이 k보다 크면 불가능 -> return

private void dfs(int r, int c, int depth, int k){
        
        if(answer != null) return;
        if(depth + distance(r, c, endRow, endCol) > k) return; //현재 깊이 + 남은 거리 > k
        if(k == depth) {
            answer = route.toString();
            return;
        }
        for(int i=0; i<4; i++){
            
            int nextRow = r + rdir[i];
            int nextCol = c + cdir[i];
            if(nextRow <= arrRow && nextCol <= arrCol && nextRow > 0 && nextCol >0){
                route.append(dir[i]);
                dfs(nextRow, nextCol, depth+1, k);
                route.delete(depth, depth+1);
            }
            
        }

 }

💻 전체 코드

import java.util.*;
import java.lang.*;
class Solution {
    int[][] array;
    String answer = null;
    StringBuilder route;
    char[] dir = {'d', 'l', 'r', 'u'};
    int[] rdir = {1, 0, 0, -1};
    int[] cdir = {0, -1, 1, 0};
    int endRow, endCol;
    int arrRow, arrCol; //미로 길이
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        route = new StringBuilder();
        array = new int[n][m];
        endRow = r; endCol = c;
        arrRow = n; arrCol = m;
        //최단거리 계산 - 거리 k로 갈 수 있는지 여부
        int length = distance(x, y, r, c);
        if((k - length) % 2 == 1 || k < length) return "impossible";
        dfs(x, y, 0, k);
        
        return answer == null ? "impossible" : answer;
    }

    private int distance(int x, int y, int r, int c){
        return (int)Math.abs(x-r) + (int)Math.abs(y-c);
    }

    private void dfs(int r, int c, int depth, int k){
        
        if(answer != null) return;
        if(depth + distance(r, c, endRow, endCol) > k) return; //현재 깊이 + 남은 거리 > k
        if(k == depth) {
            answer = route.toString();
            return;
        }
        for(int i=0; i<4; i++){
            
            int nextRow = r + rdir[i];
            int nextCol = c + cdir[i];
            if(nextRow <= arrRow && nextCol <= arrCol && nextRow > 0 && nextCol >0){
                route.append(dir[i]);
                dfs(nextRow, nextCol, depth+1, k);
                route.delete(depth, depth+1);
            }
            
        }

    }




}