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

풀이

1. 4방탐색/bfs
2. visit 배열 대신 최저 값을 가지고 있는 2차원 int 배열 min을 사용
   • 지금 비용이 min에 저장되어 있는 값보다 크면 continue
3. dr, dc로 선언한 방향의 index가 상-0, 하-1, 좌-2, 우-3으로 index/2 값이 같으면 100원만, 다르면 600원 추가
   • 여기서 상하/좌우 따질 필요없이 직전의 d와 현재 d만 같으면 100원 나머지는 600원 해도 될 듯
   • 어차피 직전 d의 반대방향일 경우 min[][]의 값이 올라서 쓸모 없어짐

 

비고

• if (min[nr][nc] < cost) continue;
  • 처음에는 <=로 했다가 <로 변경
  • 값이 같아도 들어오는 방향에 따라 이후 추가되는 값이 달라질 수도 있기 때문

 

package KakaoIntern2020.P67258_경주로건설;

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

public class Solution {

	static public int solution(int[][] board) {
		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };
		int N = board.length;

		Queue<Node> que = new LinkedList<>();
		int[][] min = new int[N][N];
		que.offer(new Node(0, 0, -1, 0));

		for (int i = 0; i < N; i++) {
			Arrays.fill(min[i], Integer.MAX_VALUE);
		}

		while (!que.isEmpty()) {
			int size = que.size();
			for (int s = 0; s < size; s++) {
				Node cur = que.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur.r + dr[d];
					int nc = cur.c + dc[d];

					int cost = cur.cost + 100;
					if (cur.d != -1 && cur.d / 2 != d / 2)
						cost += 500;

					if (!check(nr, nc, N) || board[nr][nc] == 1)
						continue;

					if (min[nr][nc] < cost)
						continue;

					que.offer(new Node(nr, nc, d, cost));
					min[nr][nc] = cost;
				}
			}
		}

		return min[N - 1][N - 1];
	}

	static boolean check(int r, int c, int N) {
		if (r >= 0 && r < N && c >= 0 && c < N)
			return true;
		return false;
	}

	static class Node implements Comparable<Node> {
		int r, c, d, cost;

		public Node(int r, int c, int d, int cost) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
			this.cost = cost;
		}

		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}

	}

	public static void main(String[] args) {
		int[][] b = { { 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 } };
		System.out.println(solution(b));
	}

}