[Java] 프로그래머스 미로 탈출 명령어

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

2023 KAKAO BLIND RECRUITMENT 기출문제 

알아야 할 개념

• DFS 

풀이

로직은 다음과 같다. 

1. 거리 배열 dx, dy 를 주어진 순서대로 생성한다. // 아래, 왼쪽, 오른쪽, 위
2. 4방향 탐색 dfs 함수를 만들어 탐색한다. 
3. 현재 위치에서 end 지점까지 도달할 수 없으면 탐색하지 않는다. 
4. 더이상 이동할 수 없고, end 지점에 도달했으면 답을 리턴한다. 

문제에서 요구하는 dfs 방법이 신선했다. (역시 카카오 기출 )

조건을 보면 눈여겨야할 조건들 두 개가 있다. 

• 한번 방문한 곳을 다시 한 번 방문할 수 있다. 
• 4방향 탐색할 때는 down, left, right, up( 사전순 ) 으로 탐색하여야 한다. 

dfs 예시.

태블릿에다가 요리 저리 시뮬레이션 해 본 결과 다음과 같은 사실을 알았다.

다음과 같이 k, cnt 변수가 있을때 " 현재 지점 cur(x , y) 에서 end (x,y)까지 거리 k, cur(x,y) 에서 움직 일 수 있는 횟수 cnt " 

• k  >  cnt 이면 도달 불가능하다. 
• cnt - k 가 홀수 이면 도달 불가능하다.

도달 불가능할 때 설명.

재귀 호출을 할 때 nextPosition next MovingCount 환경에서 도달 가능할때만 호출을 하는것으로 dfs 최적화를 해야 문제가 풀린다. 

코드

자바

class Solution {
    //d l r u
    int[] dx = {1,0,0,-1};
    int[] dy = {0,-1,1,0};
    Character[] posChar = {'d','l','r','u'};
    boolean stop = false;
    String answer = "impossible";
    int n , m,sx,sy,ex,ey;
    //n x m
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.n = n;
        this.m = m;
        sx = x-1;
        sy = y-1;
        ex = r-1;
        ey = c-1;
        
        if(sx == ex && sy == ey)return "";
        if(!canArrival(sx,sy,k)) return answer;
        helper(sx,sy,k-1,"");
        return answer;
    }
    //거리, 움직일 횟수
    public boolean canArrival(int cx, int cy, int k){
        int d = getD(cx,cy,ex,ey);
        if(d > k || (k-d) % 2 == 1 )return false;
        else return true;
    }
    public int getD(int ax, int ay, int bx, int by){
        return Math.abs(ax - bx) + Math.abs(ay - by);
    }
    
    public void helper(int x, int y ,int cnt, String cur){
        if(stop || cnt < 0)return;
        
        for(int k = 0 ; k < 4 ;k++){
            if(stop)return;
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx < 0 || ny < 0 || nx > n-1 
               || ny > m-1 || !canArrival(nx,ny,cnt) )continue;
            if(cnt > 0)
                helper(nx, ny, cnt-1, cur+posChar[k]);
            //System.out.println("현재 문자"+cur+"위치"+nx+","+ny+"cnt:"+cnt+"목표"+ex+",");
            if(nx == ex && ny == ey && cnt ==0){
                stop = true;
                answer = cur+posChar[k];
                return;
            }
        }
    }
}