[프로그래머스]경주로 건설 - JAVA

[프로그래머스]경주로 건설 - JAVA

programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

풀이

최소 비용을 구하는 문제이므로 모든 경우를 다 탐색하는 dfs 보단 최단거리를 찾는 bfs가 적합하다. 

Node라는 클래스를 만들어 주어 현재 노드에 대한 x, y 좌표와 현재까지의 비용, 방향 정보를 담아 주었다.

 

여기서 중요한 점은 기존의 bfs랑은 다르게 이미 방문한 노드도 재 방문이 가능하다는 점이다. 재 방문을 했을 때의 비용이 현재 비용보다 작거나 같으면 그 방향으로 계속 가도 괜찮다는 의미이고 재 방문을 했을 때의 비용이 더 크면 그 방향으로는 더 가지 말라는 의미이므로 q에 노드를 넣어주면 안된다. 

 

방문 했는지 여부를 visited 함수를 사용해 체크하였고 첫 방문이거나, 재 방문일 경우 그 방향으로 갈 수 있는 경우라면 값을 갱신해 주었다. 

 

이 문제에서 가장 시간을 많이 빼앗긴 부분은 cost를 계산하는 부분이었다. 나는 직선으로 움직일때는 100원, 코너일때는 500원을 더해주도록 계산하였는데 문제를 자세히 읽어보면 코너를 만들때 500원이 '추가'로 든다. 즉 코너일때 비용이 기존 비용의 500원이 증가하는 것이 아니라 기존 직선 비용인 100원에 500원을 추가한 600원이 되는 것이다. 이것 때문에 계속 틀렸다... 문제를 자세히 읽자.

 

코드

import java.util.*;
 
class Solution {
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    boolean[][][] visited;
    int N;
    
    public int solution(int[][] board) {
        init(board.length);
        return bfs(board);
    }
    
    public void init(int n) {
        visited = new boolean[n][n][4];
        N = n;
    }
    
    public int bfs(int[][] board) {
        Queue<Node> q = new LinkedList<>();
        visited[0][0][0] = visited[0][0][1] = visited[0][0][2] = visited[0][0][3];
        q.add(new Node(0, 0, -1, 0));
        
        int min_cost = Integer.MAX_VALUE;
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.x == N - 1 && current.y == N - 1) min_cost = Math.min(min_cost, current.cost);
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < N && ny < N && board[nx][ny] != 1) {
                    int next_cost = 0;
                    if(current.dir == i || current.dir == -1) next_cost = current.cost + 100; //직선
                    else  next_cost = current.cost + 600; //곡선
                    
                    if(!visited[nx][ny][i] || board[nx][ny] >= next_cost) {
                        q.add(new Node(nx, ny, i, next_cost));
                        visited[nx][ny][i] = true;
                        board[nx][ny] = next_cost;
                    }
                }
            }
        }
        return min_cost;
    }
    
    public class Node {
        int x, y, dir, cost;
        
        public Node(int x, int y, int dir, int cost) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cost = cost;
        }
    }
}