Programmers 67259: 경주로 건설

N x N 크기의 정사각형 격자 형태에서 (0, 0) ~ (N-1, N-1)까지 경주로를 만드는데

직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 든다.

경주로를 만드는 데 최소 비용을 구하는 문제이다.

 

1차 시도 - BFS로 모든 방향에 대한 비용을 구하면서 재방문의 경우는 제외해주도록 한다. -> O(3^N)이 걸릴 것이기 때문에 시간 초과..

심지어 정확도도 틀림

import java.util.*;
class Solution {
	public static int dr[] = { 0, 1, 0, -1 };
	public static int dc[] = { 1, 0, -1, 0 };

	public int solution(int[][] board) {
		Queue<Move> queue = new LinkedList<Move>();
		for (int i = 0; i < 4; i++) {
			queue.add(new Move(dr[i], dc[i], i, 100)); // 이 부분이 벽일 수도 있기 때문에 정확도가 틀린 것이었다.
		}

		int min = Integer.MAX_VALUE;
		int length = board.length;

		while (!queue.isEmpty()) {
			Move now = queue.poll();

			if (now.row == length - 1 && now.col == length - 1) {
				min = Math.min(min, now.value);
			}

			for (int i = 0; i < 4; i++) {
				if (Math.abs(i - now.direction) == 2) {
					continue;
				}

				int newRow = now.row + dr[i];
				int newCol = now.col + dc[i];
				int newValue = now.direction == i ? 100 : 600;
				newValue += now.value;

				if (isBoundary(newRow, newCol, length) && newValue > 0 && newValue < min
						&& board[newRow][newCol] == 0) {
					queue.add(new Move(newRow, newCol, i, newValue));
				}
			}

		}

		return min;
	}

	public boolean isBoundary(int row, int col, int N) {
		if (row < 0) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (row >= N) {
			return false;
		}
		if (col >= N) {
			return false;
		}
		return true;
	}
}

class Move {
	int row;
	int col;
	int direction;
	int value;

	public Move(int row, int col, int direction, int value) {
		this.row = row;
		this.col = col;
		this.direction = direction;
		this.value = value;
	}
}

채점 결과

정확성: 30.4

합계: 30.4 / 100.0

 

 

 

2차시도 - 재 방문을 줄이자 => DP를 사용해볼까? 그런데 방향마다 더해지는 값이 달라서 DP에도 다르게 저장해야함

DP[i][j][k]: (0, 0) ~ (i, j)까지 k방향으로 움직였을 때 최소비용이라고 정의하도록 하자

import java.util.*;
import java.util.*;

class Solution {
	public static int dr[] = { 0, 1, 0, -1 };
	public static int dc[] = { 1, 0, -1, 0 };

	public int solution(int[][] board) {

		int min = Integer.MAX_VALUE;
		int length = board.length;

		int dp[][][] = new int[length][length][4];

		Queue<Move> queue = new LinkedList<Move>();
		for (int i = 0; i < 4; i++) {
			queue.add(new Move(0, 0, i, 0));
		}

		while (!queue.isEmpty()) {
			Move now = queue.poll();

			if (now.row == length - 1 && now.col == length - 1) {
				min = Math.min(min, dp[now.row][now.col][now.direction]);
			}

			for (int i = 0; i < 4; i++) {
				if (Math.abs(i - now.direction) != 2) { // 후진 제외
					int newRow = now.row + dr[i];
					int newCol = now.col + dc[i];
					int newValue = (now.direction == i ? 100 : 600) + now.value;

					if (isBoundary(newRow, newCol, length) && board[newRow][newCol] == 0) {
						if (dp[newRow][newCol][i] >= newValue || dp[newRow][newCol][i] == 0) {
							dp[newRow][newCol][i] = newValue;
							queue.add(new Move(newRow, newCol, i, newValue));
						}
					}
				}
			}
		}

		return min;
	}

	public boolean isBoundary(int row, int col, int N) {
		if (row < 0) {
			return false;
		}
		if (col < 0) {
			return false;
		}
		if (row >= N) {
			return false;
		}
		if (col >= N) {
			return false;
		}
		return true;
	}
}

class Move {
	int row;
	int col;
	int direction;
	int value;

	public Move(int row, int col, int direction, int value) {
		this.row = row;
		this.col = col;
		this.direction = direction;
		this.value = value;
	}
}