LV3 [KAKAO] 경주로 건설

---

문제

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

프로그래머스

풀이

dfs 에 dp 테크닉을 조금 섞은 문제였다.

 

우선 경로에 따른 값 처리를 생각했다.

직선도로 같은 경우에는 방문한 칸 - 1 개였다.

만약 7칸을 방문한다면 코너와 상관없이 직선코너는 6개가 있다.

 

코너같은 경우에는 이전에 내가 어느 방향에서 왔는지를 기억하고, 그에 따라서 코너인지 아닌지 판단하기로 했다.

만약 왼쪽에서 오른쪽으로 왔는데 내가 갈려는 방향이 오른쪽이면 같은 방향이므로 코너로 체크하지 않고, 그 외에는 코너로 체크한다.

 

처음에는 visited 배열하나를 이용해서 최솟값을 찾아 리턴하려고 했으나, 적절한 탈출문이 없어서 시간초과가 났다.

 

그 다음으로 해본것은 중간 비용이 저장해놓은 값보다 크다면 바로 return하는 식으로 탈출조건을 추가했다. 그러나 이마저도 몇개의 케이스는 시간초과가 발생했다.

 

최대한 재귀 레벨을 낮추기 위해서는 함수호출을 부르기전에 검사하는 로직이 필요하다고 생각했고, 각 칸의 값들을 저장하는 2차원 dp배열을 하나 만들었다. 이 배열의 각 칸들은 유사(?)최솟값을 지니고 있다.

 

왜 유사최솟값이라고 표기했냐면 오는 방향에 따라서 더 큰값이라도, 다음칸은 더 작은값을 만들 수 있기 때문이다.

 

위 사진을 보자. 빨간 루트와 파란 루트가 만나는 지점에서 빨간 루트는 1300원이라고 가정하고, 파란루트는 1400원이라고 가정해보자. 

 

다음칸의 빨간 루트는 코너를 만나기에 직선 + 코너로 600원을 추가하여 1900원지만, 파란루트는 직선으로 가기에100원만 추가해서 1500원이 된다. 이와같이 직선코너로 왔을때는 지금값이 더 비싸더라도 다음칸에는 더 저렴해질 수 있다.

따라서 같은 방향으로 왔을때는 비용 검사를 하지 않고 재귀를 수행한다. 방향이 다를 경우에는 비용을 비교해서 수행할지 말지를 결정하면 된다.

 

코드

class Solution {
    public int[] dx = {0, 0, 1, -1};
    public int[] dy = {1, -1, 0, 0};
    public int[][] mem;

    public int answer = Integer.MAX_VALUE;

    public void dfs(int x, int y, int[][] board, boolean[][] visited, int n, int from, int cost){
        if(x == n-1 && y == n-1){
            this.answer = Math.min(this.answer, cost);
            return;
        }

        if(cost > answer) return;

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 범위 안에 들어왔으며, 벽이 아니며, 방문하지 않은 칸인경우.
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0 && !visited[nx][ny]){
                visited[nx][ny] = true;
                if(from == i || from == -1){ //같은 방향일경우
                        mem[nx][ny] = cost+100;
                        dfs(nx, ny, board, visited, n, i, cost + 100);
                } else{ // 다른 방향일경우
                    if(mem[nx][ny] >= cost+600){
                        mem[nx][ny] = cost + 600;
                        dfs(nx, ny, board, visited, n, i, cost + 600);
                    }
                }
                visited[nx][ny] = false;
            }
        }
    }

    public void memInit(int l){
        mem = new int[l][l];
        for(int i=0; i<l; i++){
            for(int j=0; j<l; j++){
                mem[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    public int solution(int[][] board) {
        int l = board.length;
        this.memInit(l);
        boolean[][] visited = new boolean[l][l];
        visited[0][0] = true;
        dfs(0, 0, board, visited, l, -1, 0);

        return this.answer;
    }
}

 

후기

 

비교적 익숙했던 그래프 문제라 1시간 내외로 풀이했다.

 

그리고 테케에서 디버깅하다가 예외를 빨리 찾을 수 있었다. 사실 그게 아니라면 또 오래걸렸을 거 같긴하다.

 

자바로 그래프 문제를 풀어보고 싶었는데 해보니 크게 다른게 없어서 안심했다.