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

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

프로그래머스

완전탐색을 하면 시간초과가 발생하는 문제이다. bfs와 dfs 중 원하는 것을 골라서 풀 수 있다.

 

 

핵심

bfs든 dfs든 break 포인트를 걸어주어야지만 시간초과를 막을 수 있다. 또한 사전순으로 탐색하기에 탐색 조건의 순서를 사전순으로 배치하면 더 쉽게 풀 수 있다. 이 문제에서 재미있는 점은 방문한 곳을 한 번 더 방문할 수 있다는 것이다. 다만 k번의 움직임만에 도달해야 하기에 남은 거리 + 깊이에서 k를 뺀 값이 2로 나누어져야 한다. -> 도달하거나, 도달한 뒤 다른 곳으로 갔다가 다시 돌아옴(짝수)

 

정답 코드

public class Solution {
    private final String[] dirName = {"d", "l", "r", "u"};
    private final int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    private StringBuilder answer;
    private String result;
    private int endRow;
    private int endCol;
    private int mapRow;
    private int mapCol;

    public 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;

        int distance = getDistance(x, y);

        if (distance > k || (k - distance) % 2 == 1) {
            return "impossible";
        }
        dfs(x, y, 0, k);

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

    private int getDistance(int x, int y) {
        return Math.abs(x - endRow) + Math.abs(y - endCol);
    }

    private void dfs(int row, int col, int depth, int limit) {
        if (result != null) {
            return;
        }
        if (depth + getDistance(row, col) > limit) {
            return;
        }
        if (limit == depth) {
            if (row == endRow && col == endCol) {
                result = answer.toString();
            }
            return;
        }
        for (int i = 0; i < dir.length; i++) {
            int nowRow = row + dir[i][0];
            int nowCol = col + dir[i][1];
            if (0 < nowRow && nowRow <= mapRow && 0 < nowCol && nowCol <= mapCol) {
                answer.append(dirName[i]);
                dfs(nowRow, nowCol, depth + 1, limit);
                answer.delete(depth, depth + 1);
            }
        }
    }
}

해설

우선 주로 사용되는 변수들은 전역변수로 설정하여 편하게 사용하였다.

첫 시작에서 이동할 수 있는 카운트가 거리보다 작거나 홀수면 바로 불가능하다는 표시를 하고 종료시킨다.

dfs를 시작했다는 것은 답이 나온다는 의미이기도 하다.

이동한 경로를 answer에 넣어주면서 재귀호출을 한다.

이때 다음 이동경로에서 목적지에 도달할 수 없다면 return 해준다.

만약 목적지에 도달한다면 그것이 정답이 되기에 바로 result에 넣어준다.

이후에는 모든 재귀호출이 result에 값이 있기에 전부 빠져나오게 된다.

여기서 처음 도달한 것이 정답인 이유는 앞서 말했듯이 사전순으로 탐색하기에(밑, 왼, 오, 위) 가장 먼저 도달한 것을 정답으로 채택한다.

 

배운 점

처음에 문제를 보고 break문이 없다면 당연하게도 시간초과가 날것이라 생각했다.

다행히도 break조건을 쉽게 찾아서 설계하는 단계가 어렵지는 않았다.

다만 매개변수가 많기도 하고 2차원배열을 다루다 보니 어디를 x, y로 두었는지 혼동하여 실수를 하였다.

이러한 부분의 실수를 줄여야겠다.