[프로그래머스/Level3] 경주로 건설 (JAVA)

📖 문제

프로그래머스

 

 

 

 

💡  풀이 방식

• BFS + DP

4가지 방향에서 오는 방향 별 최소 비용을 저장하기 위해 방향까지 합친 3차원 배열을 사용하는 것이 포인트!

이 때, 단순 bfs로만 탐색하면 각 방향마다 달라지는 최소 비용을 지나칠 수 있으므로 dp (메모이제이션)을 사용한다.

 

- 4방향 탐색을 할 때, 처음 실행하거나 방향이 바뀌지 않은 경우에는 현재 비용에서 +100원만큼, 방향이 바뀐 경우에는 +600원만큼 이동하도록 한다. (방향 전환하느라 +500, 직진하느라 +100 한 번 더 하므로)

int nextCost = now.cost;

// 처음 실행하거나, 방향이 그대로인 경우
if(now.dir == -1 || now.dir == d) {
    nextCost += 100;
}
else {  // 방향이 변한 경우
    nextCost += 600;
}

 

 

- 그리고 해당 방향으로 방문한 적 없고, 기존 금액 board[nr][nc] 보다 새로운 금액 nextCost 이 더 적은 경우, 격자의 칸을 방문 처리하고, 큐에 값을 추가하고, 칸의 값도 새로운 금액으로 채운다.

if(visited[nr][nc][d] == 0 || board[nr][nc] >= nextCost) {
    q.add(new Node(nr, nc, d, nextCost));
    visited[nr][nc][d] = 1;
    board[nr][nc] = nextCost;
}

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N;
    static int[][] board;
    static int[][][] visited;
    
    public int solution(int[][] board) {
        this.board = board;
        N = board.length;
       
        visited = new int[N][N][4]; // 4방향에 대한 값 저장
         
        return bfs();
    }
    
    private static int bfs() {
        int answer = Integer.MAX_VALUE;
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(0,0,-1,0));
        
        while(!q.isEmpty()) {
            Node now = q.poll();
            
            // 도착점에 도달한 경우
            if(now.r == N-1 && now.c == N-1) {
                answer = Math.min(answer, now.cost);
            }
            
            for(int d = 0 ; d < 4 ; d++) {
                int nr = now.r + dx[d];
                int nc = now.c + dy[d];
                
                if(nr < 0 || nr >= N || nc < 0 || nc >= N || board[nr][nc] == 1)  continue;
                
                int nextCost = now.cost;
                
                // 처음 실행하거나, 방향이 그대로인 경우
                if(now.dir == -1 || now.dir == d) {
                    nextCost += 100;
                }
                else {  // 방향이 변한 경우
                    nextCost += 600;
                }
                
                // 해당 방향으로 방문한 적 없고, 기존 금액보다 새 금액이 더 적어서 이득인 경우 큐에 추가하기
                if(visited[nr][nc][d] == 0 || board[nr][nc] >= nextCost) {
                    q.add(new Node(nr, nc, d, nextCost));
                    visited[nr][nc][d] = 1;
                    board[nr][nc] = nextCost;
                }                
            }
        }
        
        return answer;
    }
}
 
class Node {
    int r, c, dir, cost;
    
    public Node(int r, int c, int dir, int cost) {
        this.r = r;
        this.c = c;
        this.dir = dir;
        this.cost = cost;
    }
}

 

 

➕ 다른 풀이 방식

우선순위 큐를 사용하신,,

프로그래머스 :: 경주로 건설 (Java)

 

---

💦 어려웠던 점

- bfs로만 풀 생각을 해서 틀렸었다....

 

 

🧐 새로 알게 된 내용

- 3차원 배열을 활용해 4방향에서 오는 방향 별 최소 비용을 구하고, dp를 사용하는 아이디어!

- 더욱 작은 값을 가질 수 있다면, 그 값을 들고 다시 방문할 수도 있다고 한다.

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[카카오][BFS/DP][lv.3] 경주로 건설 - 자바(Java)

 

[카카오 인턴] 경주로 건설 - JAVA