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

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

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

생각

DFS에 DP를 섞어서 좀 끄적이다가 잘 안돼서 바로 BFS로 돌렸더니 풀었습니다..

다시 생각해보니 최소의 비용으로 가야 하기때문에 BFS + DP 방식으로 구현해야합니다

 

주의할점은 도착점에 도달하면 바로 BFS를 리턴시키는게 아니라 다른 경로로 오고 비용이 더 적을 경우가 있을 수 있으므로 continue 시켜줘야 합니다!!

 

1. 시작지점에서 오른쪽방향, 아래방향으로 진행할 수 있으므로 방향 인덱스를 파라미터로 받는 BFS 함수를 만들어줍니다.

2. 시작위치에서 비용을 0으로 넣고 dp[y][x] = 1 로 벽을 만들어줍니다. 그 다음 현재위치에서 사방탐색을 하여 갈수있으는곳이 지금 방향과 같다면 직선 경로이므로 비용을 + 100 시켜줍니다. 지금 방향과 같지 않다면 곡선 경로이므로 비용을 + 600 증가시켜줍니다.

3. dp[ny][nx] == 0 이면 처음가는곳이므로 dp[ny][nx]에 계산한 비용(nextCost)을 넣어주고 큐에도 넣어줍니다. dp[ny][nx] > nextCost 이면 더 작은값으로 온 경우이므로 작은 값으로 갱신시켜줍니다. (dp[ny][nx] = nextCost) 큐에도 넣어줍니다.

4. 큐에서 꺼낸 객체의 좌표가 도착점이라면 비용을 비교하여 더 작은값을 업데이트 시켜줍니다. 그 다음으로 return 하는게 아니라 continue 시켜줘 큐에 남아있는 좌표들의 가능한 경로를 탐색합니다.

 

Java Code

package com.java.algorithm;

import java.util.LinkedList;
import java.util.Queue;

public class Programmers_경주로건설 {
	static int N;
	static int[][] dp;
	static int[] dy = {-1,1,0,0}; //위 아래 왼 오
	static int[] dx = {0,0,-1,1}; //위 아래 왼 오
    static int ans;
    
    public static class Pos{
		int y,x;
		int dir;
		int cost;
		
		public Pos(int y, int x, int dir, int cost) {
			this.y = y;
			this.x = x;
			this.dir = dir;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", dir=" + dir + ", cost=" + cost + "]";
		}

		
    }
    public static void main(String[] args) {
		int[][] board = {
				{0,0,0},
				{0,0,0},
				{0,0,0},
		};
		System.out.println(solution(board));
	}
    public static int solution(int[][] board) {
        
        N = board.length;
        dp = new int[N][N];
        
        ans = Math.min(byBFS(0, 0, 1, board), byBFS(0, 0, 3, board));
        
        return ans;
    }
    
    public static int byBFS(int y, int x, int dir, int[][] board) {
    	Queue<Pos> q = new LinkedList<>();

    	q.add(new Pos(y,x,dir,0));
    	dp[y][x] = 1; // 시작위치를 벽으로 만들기
    	int cost = Integer.MAX_VALUE;
    	while(!q.isEmpty()) {

			Pos now = q.poll();

			int nowY = now.y;
			int nowX = now.x;
			int nowDir = now.dir;
			int nowCost = now.cost;
			
			if(nowY == N-1 && nowX == N-1) {
				if(cost > nowCost) {
					cost = nowCost;
				}
				continue;
			}
			
	    	for (int d = 0; d < 4; d++) {
				int ny = nowY + dy[d];
				int nx = nowX + dx[d];
				
				int nextCost = 0;
				
				if(ny >= N || ny < 0 || nx >= N || nx < 0 || board[ny][nx] == 1) continue;
				
				if(nowDir == d) {
					nextCost = nowCost + 100;
				}else {
					nextCost = nowCost + 600;
				}
				//처음가는곳이면 큐에 넣어줌
				if(dp[ny][nx] == 0) {
					dp[ny][nx] = nextCost;
					q.add(new Pos(ny, nx, d, nextCost));
				}else if(dp[ny][nx] >= nextCost) {
					dp[ny][nx] = nextCost; // 더 작은 값으로 갱신
					q.add(new Pos(ny, nx, d, nextCost));
				}
				
			}
    		
    	}
    	return cost;

    }
}