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

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

프로그래머스

외부 IDE (like. IntelliJ..) 없이 코테를 보는 기업들을 위해 프로그래머스로 문제를 풀어보기 시작...

 

🏗️ 설계

• DFS를 통해서 풀이를 하려고 하였습니다.
• 방문한 곳을 또 방문할 수 있는데 어떻게 케이스를 줄여나갈 수 있을까...
  => 가능하지 않은 케이스들을 백트래킹을 통해서 풀이
  => 남은 거리 > 목표 횟수 - 현재 이동 횟수 or (목표 횟수 - 현재 이동 횟수) - 남은거리가 홀수 라면 불가능한 경우

📋 코드

class Solution {
    // (x,y) : 시작점
    // (r,c) : 종료점
    // (n,m) : 격자의 크기
    // k : 탈출까지 이동해야하는 거리
    static boolean flag = false;
    static int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    static char[] appendVal = {'d', 'l', 'r', 'u'};
    static StringBuilder sb = new StringBuilder();
    static String retVal = new String("impossible");
    
    static class Pos {
        int x;
        int y;
        
        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
    }
    
    public int distance(Pos pos1, Pos pos2) {
        return Math.abs(pos1.x - pos2.x) + Math.abs(pos1.y - pos2.y);
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        Pos startPos = new Pos(x, y);
        Pos endPos = new Pos(r, c);
        
        dfs(startPos, endPos, n, m, 0, k);
        
        String answer = retVal;
        
        return answer;
    }
    
    public boolean inRange(int x, int y, int xSize, int ySize) {
        return x > 0 && x <= xSize && y > 0 && y <= ySize;
    }
    
    public void dfs(Pos curPos, Pos endPos, int xSize, int ySize, int curCnt, int targetCnt) {
        if (flag)
            return;
        
        int remainDist = distance(curPos, endPos);
        
        // 남은 거리가 (목표 횟수 - 현재 이동 횟수)보다 크다면 불가능
        if (remainDist > (targetCnt - curCnt))
            return;
        // ((목표 횟수 - 현재 이동 횟수) - 남은 거리) 가 짝수가 아니라면 불가능
        if (((targetCnt - curCnt) - remainDist) % 2 != 0)
            return;
        
        // 결과값 도달
        if (curCnt == targetCnt) {
            if (curPos.x == endPos.x && curPos.y == endPos.y) {
                flag = true;
                retVal = sb.toString();
            }
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int newX = curPos.x + dir[i][0];
            int newY = curPos.y + dir[i][1];
            
            if (inRange(newX, newY, xSize, ySize)) {
                sb.append(appendVal[i]);
                dfs(new Pos(newX, newY), endPos, xSize, ySize, curCnt + 1, targetCnt);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}

👎 어려웠던 점

• 진짜 방문 했던 곳을 다시 방문하는 문제들은 풀어도 풀어도 적응이 되지 않는 것 같은 느낌은 기분탓인가...
• IDE 없이 푸려니깐 Java API 들이 생각나던 것들도 생각이 나지 않는 마법....