2023 Kakao Blind - 미로 탈출 명령어
Level: 3
Language: Java
Comment: dfs, bfs, 시뮬, 백트래킹
URL: https://programmers.co.kr/learn/courses/30/lessons/150365
전체 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/main/java/com/programmers/kakao2023/blind/Test6.java
테스트 코드: https://github.com/juhwanHeo/algorithm/blob/main/src/test/java/com/programmers/kakao2023/blind/Test6Test.java

0. 문제 설명

• 문제 URL 참고

1. 로직

I. dfs 방향

• 사전순으로 빠른 경로를 찾아야 하기 때문에
  • d, l, r, u 순으로 탐색

static String[] dirsStr = {"d" , "l", "r", "u"};
static int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};

II. dfs 종료 조건

• (1) 이동 경로가 k 인 경로가 처음 만들어 졌을 때
• (2) 깊이 + 남은 거리가 k 보다 클 때
• (3) 깊이가 k 일 때

if (result != null) return; // (1)
if (depth + distance(row, col, endRow, endCol) > limit) return; // (2)
if (limit == depth) { // (3)
    if (row == endRow && col == endCol) result = answer.toString();
    return;
}

III. dfs 깊이 탐색 + 백트래킹

for (int i = 0; i < dirs.length; i++) {
    int nRow = row + dirs[i][0];
    int nCol = col + dirs[i][1];
    if (nRow > 0 && nCol > 0 && nRow <= mapRow && nCol <= mapCol) {
        answer.append(dirsStr[i]);
        dfs(nRow, nCol, depth + 1, limit);
        answer.delete(depth, depth + 1);
    }
}

• 백 트래킹으로 ANT 찾는 과정
  
• 이런 느낌으로 경로를 찾음

VI. TC 31번 시간초과

• TC 31번이 시간초과가 나서 어떤 조건이 더 필요하다는 것을 느끼게 됨
• 거리가 k 인 경로를 탐색해야하기 때문에
  k - (시작 ~ 끝의 최단거리) 한 것이 짝수인 경우 일 때만
  거리가 k인 경로가 생길 수 있다.
  • 만약 3 x 4 미로가 주어지고, k = 4, 시작 = (1,3), 끝 = (3, 4) 로 주어지면
  • 최단거리 = 3, k - 최단 거리 = 4 - 3 = 1 (홀수)
  • 아래 그림과 같이 (3, 2)를 들렸다 와야 한다. (다른 경로로 가도 마찬가지)
    
  • 만약 3 x 4 미로가 주어지고, k = 5, 시작 = (1,3), 끝 = (3, 4) 로 주어지면
  • 최단거리 = 3, k - 최단 거리 = 5 - 3 = 2 (짝수)
  • 경로: ddlrr
    
• dfs 시작하기 전에 k - (시작 ~ 끝의 최소거리) 가 홀수 이면 impossible 을 return 하여 통과함

// TC 31
int distance = distance(x, y, endRow, endCol);
if (distance > k || (k - distance) % 2 == 1) return "impossible";
dfs(x, y, 0, k);

2. 전체 코드

/*
 * @2023 KAKAO BLIND RECRUITMENT
 * @TestName: 미로 탈출 명령어
 * @URL: https://programmers.co.kr/learn/courses/30/lessons/150365
 */
public class Test6 {
    static String[] dirsStr = {"d" , "l", "r", "u"};
    static int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    static StringBuilder answer;
    static String result;
    static int endRow, endCol, mapRow, mapCol;
    public static String solution(int n, int m, int x, int y, int r, int c, int k) {
        result = null;
        answer = new StringBuilder();
        mapRow = n;
        mapCol = m;
        endRow = r;
        endCol = c;
        // x, y : start
        // r, c : end

        // TC 31
        int distance = distance(x, y, endRow, endCol);
        if (distance > k || (k - distance) % 2 == 1) return "impossible";
        dfs(x, y, 0, k);

        return result != null ? result : "impossible";
    }

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

    static void dfs(int row, int col, int depth, int limit) {
        if (result != null) return;
        if (depth + distance(row, col, endRow, endCol) > limit) return;
        if (limit == depth) {
            if (row == endRow && col == endCol) result = answer.toString();
            return;
        }
        for (int i = 0; i < dirs.length; i++) {
            int nRow = row + dirs[i][0];
            int nCol = col + dirs[i][1];
            if (nRow > 0 && nCol > 0 && nRow <= mapRow && nCol <= mapCol) {
                answer.append(dirsStr[i]);
                dfs(nRow, nCol, depth + 1, limit);
                answer.delete(depth, depth + 1);
            }
        }
    }
}

후기

1차 코테를 볼때는 최적화를 생각못하고, 완탐을 때려버렸더니 반이상이 시간초과 나버렸다. 문제가 뜨고 다시 천천히 풀어보니 dfs 종료 조건이나, k - (시작 ~ 끝의 최단거리) 한 것이 짝수인 경우를 생각해 해결하였다.
다른 분들이 올린 O(1) 만에 해결해 버리는 코드를 봤는데 대단했다...