[프로그래머스 Level.3] 경주로 건설 (2020 카카오 인턴십) (Java)

문제 링크

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

프로그래머스

 

 

 

 

 

코딩테스트 연습 > 2020 카카오 인턴십 > 경주로 건설

 

 

 

문제 설명

 

 

 

 

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.

제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.

경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.

경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.

이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.

건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.

 

예를 들어, 아래 그림은 직선 도로 6개와 코너 4개로 구성된 임의의 경주로 예시이며, 건설 비용은 6 x 100 + 4 x 500 = 2600원 입니다.

 

 

또 다른 예로, 아래 그림은 직선 도로 4개와 코너 1개로 구성된 경주로이며, 건설 비용은 4 x 100 + 1 x 500 = 900원 입니다.

 

 

---

 

도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.

 

 

[제한사항]

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

 

---

 

입출력 예

board	result
[[0,0,0],[0,0,0],[0,0,0]]	900
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]]	3800
[[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]]	2100
[[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]]	3200

 

 

 

입출력 예에 대한 설명

 

 

입출력 예 #1

 

본문의 예시와 같습니다.

 

 

 

 

입출력 예 #2

 

 

위와 같이 경주로를 건설하면 직선 도로 18개, 코너 4개로 총 3800원이 듭니다.

 

 

 

 

입출력 예 #3

 

 

위와 같이 경주로를 건설하면 직선 도로 6개, 코너 3개로 총 2100원이 듭니다.

 

 

 

 

입출력 예 #4

 

 

붉은색 경로와 같이 경주로를 건설하면 직선 도로 12개, 코너 4개로 총 3200원이 듭니다.
만약, 파란색 경로와 같이 경주로를 건설한다면 직선 도로 10개, 코너 5개로 총 3500원이 들며, 더 많은 비용이 듭니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

// 기존에 해당 지점에 도달했던 것 보다 비용이 더 비싸더라도 진행중인 방향에 따라서 결과적으로 더 낮은 가격으로 목적지에 도달하는 방법이 있다.
// 따라서 단순히 그 위치에서의 최소 비용을 저장하면 안되고 방향이 비용에 영향을 끼치기 때문에 그 위치에서 방향 별 최소비용을 저장할 수 있도록 해야한다. 
// 방향이 cost에 영향을 주므로, 단순히 그 당시의 최소 비용을 저장하는 것이 아닌 방향정보를 포함해서 map에 저장해야 한다.
class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1}; // 좌 우 상 하
    int answer;
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        
        int[][][] map = new int[board.length][board[0].length][4];
        boolean[][][] visited = new boolean[board.length][board[0].length][4];
        
        bfs(board, map, visited);
        
        return answer;
    }
    
    public void bfs(int[][] board, int[][][] map, boolean[][][] visited) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1, 0));
        q.add(new Node(0, 0, 3, 0));
        visited[0][0][1] = true;
        visited[0][0][3] = true;
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            
            if(node.x == board.length-1 && node.y == board[0].length-1) {
                // System.out.println("cost 값 = " + node.cost);
                answer = Math.min(answer, node.cost);
            }
            
            for(int i=0; i<4; i++) {
                int nx = node.x + dy[i];
                int ny = node.y + dx[i];
                int cost = node.cost;
                
                if(nx < 0 || ny < 0 || nx >= board.length || ny >= board[0].length || board[nx][ny] == 1) continue;
                
                if(node.direct == i)
                    cost += 100;
                else
                    cost += 600;
                
                // System.out.println("dfs("+nx+","+ny+","+i+","+cost+")");
                
                if(!visited[nx][ny][i] || cost <= map[nx][ny][i]) {
                    visited[nx][ny][i] = true;
                    map[nx][ny][i] = cost;
                    q.add(new Node(nx, ny, i, cost));
                }
            }
        }
    }
    
    class Node {
        int x;
        int y;
        int direct;
        int cost;
        
        public Node(int x, int y, int direct, int cost) {
            this.x = x;
            this.y = y;
            this.direct = direct;
            this.cost = cost;
        }
    }
}
    
    
    
// bfs 방법 - 테스트 케이스 25번 실패 
// 기존에 해당 지점에 도달했던 것 보다 비용이 더 비싸더라도 진행중인 방향에 따라서 결과적으로 더 낮은 가격으로 목적지에 도달하는 방법이 있다.
class Solution1 {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1}; // 좌 우 상 하
    int[][] map;
    boolean[][] visited;
    int answer;
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        visited = new boolean[board.length][board[0].length];
        map = board;
        
        bfs();
        
        return answer;
    }
        
    public void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 4, 0));
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            
            if(node.x == map.length-1 && node.y == map[0].length-1) {
                // System.out.println("cost 값 = " + node.cost);
                answer = Math.min(answer, node.cost);
            }
            
            for(int i=0; i<4; i++) {
                int nx = node.x + dy[i];
                int ny = node.y + dx[i];
                int cost = node.cost;
                
                if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || map[nx][ny] == 1) continue;
                
                if(node.direct == 4) // 처음엔 방향없으니 4로 해서 무조건 직선
                    cost += 100;
                else if(node.direct == i)
                    cost += 100;
                else
                    cost += 600;
                
                // System.out.println("dfs("+nx+","+ny+","+i+","+cost+")");
                
                if(!visited[nx][ny] || map[nx][ny] >= cost) {
                    visited[nx][ny] = true;
                    map[nx][ny] = cost;
                    q.add(new Node(nx, ny, i, cost));
                }
            }
        }
    }
    
    class Node {
        int x;
        int y;
        int direct;
        int cost;
        
        public Node(int x, int y, int direct, int cost) {
            this.x = x;
            this.y = y;
            this.direct = direct;
            this.cost = cost;
        }
    }
}
    

// dfs 방법 - 테스트 케이스 24 실패
// 마찬가지로 기존에 해당 지점에 도달했던 것 보다 비용이 더 비싸더라도 진행중인 방향에 따라서 결과적으로 더 낮은 가격으로 목적지에 도달하는 방법이 있다.
class Solution2 {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1}; // 좌 우 상 하
    int[][] map;
    boolean[][] visited;
    int answer;
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        visited = new boolean[board.length][board[0].length];
        map = board;
        
        visited[0][0] = true;
        dfs(0, 0, 4, 0, map);
        
        return answer;
    }
    
    public void dfs(int x, int y, int direct, int cost, int[][] map) {
        if(x == map.length-1 && y == map[0].length-1) {
            // System.out.println("cost 값 = "+cost);
            answer = Math.min(answer, cost);
            return;
        }
        
        for(int i=0; i<4; i++) {  // 좌 우 상 하
            int nx = x + dy[i];
            int ny = y + dx[i];
            int ncost = cost;
            
            if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length || map[nx][ny] == 1) continue;
            
            if(direct == 4) // 처음엔 방향없으니 4로 해서 무조건 직선
                ncost += 100;
            else if(direct == i)
                ncost += 100;
            else
                ncost += 600;
            
            // System.out.println("dfs("+nx+","+ny+","+i+","+ncost+")");
            
            if(!visited[nx][ny] || ncost <= map[nx][ny]) {
                visited[nx][ny] = true;
                map[nx][ny] = ncost;
                dfs(nx, ny, i, ncost, map);
            }
        }
    }
}

 

풀이

1. 처음에는 완전탐색 bfs와 dfs를 이용하여 문제를 풀었으나 실패했다. 우선 int형 2차원 배열 map과 boolean형 2차원 배열 visited를 만들고 좌표를 움직이며 해당 좌표까지의 방문하지 않았거나 해당 좌표까지의 cost가 이미 map에 저장된 cost보다 같거나 작다면 해당 좌표로 움직여 계속해서 탐색을 진행하는 방식으로 문제를 풀었으나 bfs에서는 테스트케이스 25번이 dfs에서는 테스트케이스 24번이 실패했다. 이유는 기존에 해당 지점에 도달했던 것 보다 비용이 더 비싸더라도 진행중인 방향에 따라서 결과적으로 더 낮은 가격으로 목적지에 도달하는 방법이 있기 때문이었다.
2. 따라서 단순히 그 위치에서의 최소 비용을 저장해가면 안되고 방향이 비용에 영향을 끼치기 때문에 그 위치에서 방향별 최소비용을 저장할 수 있도록 해야한다. 방향이 cost에 영향을 주므로, 단순히 그 당시의 최소 비용을 저장하는 것이 아닌 방향정보를 포함해서 배열(map)에 저장할 필요가 있다.
3. 우선 int형 3차원 배열 map을 생성하고 boolean형 3차원 배열 visited를 생성한다. 둘 다 board의 크기와 같고 마지막에 상하좌우 방향성을 나타내기 위해 4의 크기로 생성한다.
4. 또한, 상하좌우 네 방향으로 한 칸씩 이동하기 위해 int형 배열 dx와 dy를 만들고 answer는 가장 큰 수인 Integer.MAX_VALUE로 초기화하고 해당 위치와 방향 비용을 가진 객체를 사용하기 위해 int형  x, y, direct, cost를 갖는 Node 클래스를 생성한다.
5. 그리고 bfs()를 실행한다.
6. Node를 선언타입으로 하는 Queue를 생성하고 첫 좌표는 (0, 0)이고 아래와 오른쪽 방향밖에 갈 수 없으므로 해당 좌표와 두 방향의 값을 갖는 Node를 Queue에 담고 해당 좌표와 방향의 visited를 true로 변경한다.
7. 이제 Queue가 빌 때까지 while문을 진행하며 Queue에서 첫 Node를 꺼내고 해당 Node의 좌표가 도착점이라면 answer와 해당 Node의 cost를 비교하여 최솟값을 answer에 저장하고 아니라면 해당 Node의 좌표에서 dx와 dy를 이용해 상하좌우로 한 칸씩 이동한 좌표가 board의 좌표를 벗어나지 않고 board의 값이 1이 아니라면(벽이 아니라면) 방향을 고려하여 해당 위치로 이동한 cost를 더한 후에 해당 위치까지 이동한 cost가 map에 저장된 값 이하이거나 방문하지 않았다면(visited가 false이면) visited를 true로 변경하고 map에 해당 cost를 저장한 후 큐에 해당 위치와 방향, 비용을 담은 Node를 생성하여 담아준다.
8. 큐가 빌 때까지 해당 반복문을 진행하면 answer에 최소 비용이 저장되므로 반환하면 된다.