[프로그래머스(Programmers)][자바(java)] (Lv3) 경주로 건설

 

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

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

 

문제 풀이

 

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

public class Solution {
	
	class Node {
		int i, j, s, c, d;  // straight, corner, direction ( u, d, l, r )
		Node( int i, int j, int s, int c, int d ) {
			this.i = i;  this.j = j;  this.s = s;  this.c = c;  this.d = d;
		}
	}
	
	public int solution(int[][] board) {
		final int max = Integer.MAX_VALUE;
		int n = board.length, m = board[0].length, cost, cost_m = Integer.MAX_VALUE, i, j, s, c, d, in, jn, sn, cn, dn;
		int dp[][] = new int[n][m];
		for( i = 0; i < n; i++ )
			for( j = 0; j < m; j++ )
				dp[i][j] = max;
		dp[0][0] = 0;
		int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };  // u, d, l, r
		Queue<Node> q = new LinkedList<>();
		q.add( new Node( 0, 0, 0, 0, -1 ) );  // the starting point has no direction => -1
		while( !q.isEmpty() ) {
			Node nd = q.remove();
			i = nd.i;  j = nd.j;  s = nd.s;  c = nd.c;  d = nd.d;  sn = s + 1;
			if( i == n-1 && j == m-1 ) {
				cost_m = cost_m > dp[i][j] ? dp[i][j] : cost_m;  
				continue;
			}
			for( dn = 0; dn < 4; dn++ ) {  // top 0, bottom 1, left 2, right 3
				in = i + dx[dn];  // next i
				jn = j + dy[dn];  // next j
				if( 0 > in || in >= n || 0 > jn || jn >= m || board[in][jn] == 1 )
					continue;
				cn = dn == d || d == -1 ? c : c + 1;
				cost = sn*100 + cn*500;
				if( dp[in][jn] < cost )
					continue;
				dp[in][jn] = cost;
				q.add( new Node( in, jn, sn, cn, dn ) );
			}
		}
		return cost_m;
	}
}

 

*  BFS, DP

-  각 지점에서의 도로 건설 최소 비용을 담을 dp[][] 배열 생성 ( 최솟값을 구해야 하므로 최댓값으로 초기화 )

-  (0,0)에서 (n-1,m-1)까지 Queue로 BFS 탐색 ( 도면의 범위를 벗어나거나 벽인 경우( board[i][j] == 1 )는 제외 )
   각 지점에서 직선 도로와 코너 도로의 개수를 각각 구하고 비용을 구해 dp[][]의 비용과 비교하여 최솟값을 갱신

-  BFS 하다가 현재 지점이 (n-1,m-1)일 경우, 도착점까지의 도로 건설 최소 비용( cost_m )과 dp[n-1][m-1] 비용과 비교하여 최소 비용 갱신