[Java] Programmers 코딩테스트 연습. 미로 탈출 명령어

[Java] Programmers 코딩테스트 연습. 미로 탈출 명령어

 

문   제 : 

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

 

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다.

이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 

단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

 

제한사항 (Constraint)

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

 

 

Example )

Input: [3, 4, 2, 3, 3, 1, 5]
Output: "dllrl"

///////////////////////////////////////////////

Input: [2, 2, 1, 1, 2, 2, 2]
Output: "dr"

///////////////////////////////////////////////

Input: [3, 3, 1, 2, 3, 3, 4]
Output: "impossible"

 

---

접   근 : 

DFS를 활용하여 사전순서인 "d", "l", "r", "u" 순서로 경로를 탐색한다.

그리고 목표 좌표와 현재 좌표가 맞고, 남은 이동횟수가 0이면 탐색을 종료하고 결과 List에 추가한다.

제일 먼저 찾은 답이 사전순서대로 했을 때 제일 빠른 답이다.

List의 0 번째 인덱스 값을 리턴해준다.

만약 List가 비었다면 impossible을 리턴해준다.

---

해   결 : 

DFS를 활용하여 사전순서로 경로를 탐색한다.

하지만 한 번 움직일 때마다 4방향으로 계속 탐색을 해가면 TLE 가 될 수 밖에 없다.

따라서 런타임을 줄일 수 있는 방법을 생각했다.

 

 제일 빠르게 찾은 답이 결국 사전순으로 제일 빠른 답이다.

즉, 다른 답은 찾을 필요가 없다.

따라서 답을 찾았으면, 탐색을 즉각 종료하고 바로 결과를 리턴해도 된다.

- >  정답을 찾았는지 못찾았는지의 flag 생성

 

impossible이 될 수 밖에 없는 상황을 미리 판단할 수 있다 ! !

목표까지의 이동거리가 너무 멀거나

남은 이동거리를 2로 나누었을 때 홀수라면 도착지점까지 다시 돌아올 수 없다.

- >  if문으로 처음 코드 시작할 때 체크

 

이 두 가지 방법을 사용하지 않고 돌리면 런타임이 너무 길어져서 테스트케이스를 통과하지 못한다.

 

---

 

 

결   과  :

import java.util.*;

class Solution {
    
    int[] X = new int[] {1, 0, 0, -1};
    int[] Y = new int[] {0, -1, 1, 0};
    String[] step = new String[] {"d","l","r","u"}; // 사전순
    static boolean flag = false;
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String path = "";
        ArrayList<String> s = new ArrayList<>();
        
        // imposibble check
        int er = k - Math.abs(x-r) + Math.abs(y-c);
        if(er < 0 || er % 2 != 0) return "impossible";
        
        
        dfs(n, m, x, y, r, c, k, path, s);
        
        if(s.size() == 0) return "impossible";
        else return s.get(0);
    }
    
    // (n x m) , player(x,y), destination(r,c), 남은 횟수 : k, 현재까지 움직인 수 : curMoveNum, 지나온 길: path
    public void dfs(int n, int m, int x, int y, int r, int c, int k, String path, ArrayList<String> s){
                
        if(flag == true || Math.abs(x-r) + Math.abs(y-c) > k) // 답을 이미 찾았거나 남은 거리 > 남은 이동횟수 이면 종료
            return;
        
        if( k == 0 && x == r && y == c ){ // find
            s.add(path);
            flag = true;
            return;
        }
        
        for(int i=0; i<4; i++){ // 4방향으로 뻗어가기
            if(flag) return; // 답을 찾으면 다른 방향은 할 필요가 없음
            if(x+X[i] > 0 && y+Y[i] > 0 && n >= x+X[i] && m >= y+Y[i]) // 좌표 예외처리
                dfs(n, m, x+X[i], y+Y[i], r, c, k-1, new String(path+step[i]), s);
        }
        
    }
}