[프로그래머스] 미로 탈출 명령어 / 자바

문제         

프로그래머스

1 번째 시도   

•  1. 한 번에 정답 결론내리기 힘드니
   정답 루트 다 도출 후 탐색하기
• 2. or 사전순으로 먼저 탐색하기
• 2번이 구현이 쉬으므로 2번 선택 

// [아이디어] 
// d(아래)>l(왼쪽)>r(오른쪽)>u(위쪽)
// 위치 비교 후 아래쪽으로 가야 하면 상하 움직임보다 먼저 나오기, 위쪽으로 가야 하면 상하 움직임이 위쪽보다 먼저 나오기
// 최소 이동거리와 k는 2의 배수 만큼 차이 나야 한다 아니다면 impossible!


// [구현목록]
// 1. dfs
// 2. k와 최소 거리가 둘 다 홀수 혹은 짝수인지 구별

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);
            }
            
        }

    }




}

 

배움

• 방향을 이차원 배열이 아닌 일차원 배열 두개로 표현하기!
• dfs 탐색 순서 먼저 정할 수 있다!