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;
}
}
'알고리즘 공부 > programmers' 카테고리의 다른 글
| Programmers 62050: 지형 이동 (0) | 2021.01.17 |
|---|---|
| Programmers 64062: 징검다리 건너기 (0) | 2021.01.17 |
| Programmers 12938: 최고의 집합 (0) | 2021.01.05 |
| Programmers 42898: 등굣길 (0) | 2021.01.05 |
| Programmers 17685: 자동완성 (0) | 2020.12.30 |