99클럽 코테 스터디 14일차 - 프로그래머스, 미로 탈출 명령어

문제 풀이 예상 시간보다 지나가면 다른 해석을 보고 있습니다. 

문제

풀이

문제 해석

1. n x m 크기의 미로가 주어진다.

2. xy에서 rc로 이동해야 한다.

3. 총 이동거리는 k가 되어야 한다.

4. 같은 곳을 여러 번 방문해도 된다.

5. 여러 경로가 있을 때 사전순으로 가장 앞에 위치한 것이 정답이다.

6. 탈출 할 수 없다면 impossible을 출력한다.

틀린 풀이

1. 이동하는 모든 경로를 탐색한다. dfs

2. dfs 탈출 조건은 k만큼 전부 이동하였을 때 탈출 위치에 있다면 왔던 경로 넣어줌

3. 정렬해서 출력

문제 풀이

1. 먼저 갈 수 있는 위치인지 확인함

2. 가야 할 거리가 정해져 있는 거리보다 길면 절대 못 감 impossible 출력

3. 두 개가 같다면 갈 수 있음

4. 정해져 있는 거리가 더 길때는 두 가지로 나뉜다.

    - (정해져 있는 거리 - 가야 할 거리)가 짝수면 간다.

    - 홀수면 못간다. 

    - 이유는 홀 수 일 때는 정확히 도착할 수가 없다.

5. 갈 수 있다면 문자열을 찾아야 한다. 사전순으로 d l r u를 우선적으로 찾는다.

6. 우선적이라도 만약 그곳으로 이동했을 경우 갈 수 있는 거리보다 남은 거리가 더 길어지면 넘어가야 한다.

소스코드

틀린 코드

import java.util.*;
class Solution {
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};
    static final char[] directions = {'u', 'r', 'd', 'l'};

    public String solution(int n, int m, int x, int y, int r, int c, int k) {

        //경로들 담을 List<>();
        List<String> paths = new ArrayList<>();

        dfs(n, m, x-1, y-1, r-1, c-1, k, new StringBuilder(), paths);
        if(paths.isEmpty()) return "impossible";
        paths.sort(Comparator.naturalOrder());
        return paths.get(0);

    }

    private void dfs(int n, int m, int x, int y, int r, int c, int k, StringBuilder path, List<String> paths) {
        if(path.length() == k){
            if(x == r && y ==c){
                paths.add(path.toString());
            }
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            path.append(directions[i]);
            dfs(n,m,nx,ny,r,c,k,path,paths);
            path.deleteCharAt(path.length()-1);
        }

    }
}

맞은 코드

import java.util.*;
class Solution {
    //사전 순으로 우선 순위가 d l r u
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, -1, 1, 0};
    static char[] direction = {'d','l','r','u'};
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        //사전 점검
        if(preCheck(n,m,x,y,r,c,k)) return "impossible";
        
        StringBuilder answer = new StringBuilder();
        
        //인덱스 맞추기
        x -= 1; y-=1; r-=1; c-=1;
        
        while(k > 0){
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >=n || ny >= m) continue;
                int distance = getDistance(r,c,nx,ny);
                //우선순위가 맞더라도 거리가 안되면 도착 못하니까 넘어감
                if(distance <= k-1){
                    k--;
                    x = nx;
                    y = ny;
                    answer.append(direction[i]);
                    break;
                }
                
            }
        }
        
        return answer.toString();
    }
    
    private boolean preCheck(int n, int m, int x, int y, int r, int c, int k){
        int distance = getDistance(r,c,x,y);
        //거리가 더 길면 갈 수 없음
        if(distance > k) return true;
        //같다면 갈 수 있음
        else if(distance == k) return false;
        else{
            //작다면 k-distance 해서 홀수면 못감
            if((k-distance)%2 == 0) return false;
            else return true;
        }
    }
    
    private int getDistance(int r, int c, int x, int y){
        return Math.abs(r-x) + Math.abs(c-y);
    }
}

 

 

TIL

• 다들 참 똑똑하다. 천재같음
• dfs는 너무 쉬운 풀이이긴 했다. 생각의 전환이 빨라야 할 것 같다. 너무 매몰되지 말자