99클럽 코테 스터디 14일차 TIL [DFS]

- 오늘의 학습 키워드 : DFS

[문제 이름 : 미로 탈출 명령어 (프로그래머스 150365, LV 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/150365

내가 작성한 코드는 아래와 같다.

import java.util.*;
class Solution {
    String answer = null;
    StringBuilder route = new StringBuilder();
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, -1, 1, 0};
    char[] move = {'d', 'l', 'r', 'u'};
    // 도착 지점
    int endX, endY;
    // 미로 길이
    int n, m;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.endX = r;
        this.endY = c;
        this.n = n;
        this.m = m;
        
        int length = distance(x, y, r, c);
        // 최단거리 계산 -> k로 도착할 수 있는지 여부 판단
        if((k - length) % 2 == 1 || k < length) return "impossible";
        dfs(x, y, 0, k);

        return answer == null ? "impossible" : answer;
    }

    private void dfs(int r, int c, int depth, int k){
        if(answer != null) return;
        // 현재 깊이 + 남은 거리 > k
        if(depth + distance(r, c, endX, endY) > k) return; 
        if(k == depth) {
            answer = route.toString();
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = r + dx[i];
            int ny = c + dy[i];
            if(nx <= n && ny <= m && nx > 0 && ny >0){
                route.append(move[i]);
                dfs(nx, ny, depth+1, k);
                route.delete(depth, depth+1);
            }
        }
    }

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

풀이 과정 (풀이 시간 : 1시간 30분)

2차원 배열을 굳이 생성하지 않고도 풀 수 있는 문제였다. 시간 초과가 계속 나서, 고민 끝에 다른 사람의 블로그를 참조하였다 ㅠㅠ ..

문제의 숨은 조건을 찾아보면 다음과 같다.

- impossible이 나오는 경우

(1) 목표 거리인 k와 '시작 지점 - 목표 지점 간 거리'의 차이가 홀수인 경우

(2) k가 최단 거리보다 짧은 경우

 

이후, 사전 순으로 탐색을 위해 d -> l -> r -> u 순서로 탐색한다. 이렇게 탐색하게 되면, 사전 순으로 탐색하기 때문에 최종 결과물은 사전 순으로 제일 앞에 있는 결과 값을 도출할 수 있다.

 

1. k - ('시작 지점, 목표 지점 간 거리 차)가 홀수인 경우거나, 최단 거리가 k보다 긴 경우 impossible을 리턴한다.

2. DFS 탐색을 진행하는데, '현재 깊이' + '현 위치에서 목적 지점까지 최단 거리의 합' > k인 경우에는 바로 리턴한다.

[참고 블로그]

https://velog.io/@ji-yeon224/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%EB%AA%85%EB%A0%B9%EC%96%B4-JAVA

내일은 SSAFY 지원을 위한 자기소개서를 작성할 예정이다.