내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Solution {
public int solution(int[][] board) {
int answer = Integer.MAX_VALUE;
int N = board.length;
// 방향 아래 0, 오른쪽 1, 위 2, 왼쪽 3
int[][] d = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int[][] arr = new int[N][N];
boolean[][][] visited = new boolean[N][N][4];
for (int i = 0; i < N; i++) {
Arrays.fill(arr[i], Integer.MAX_VALUE);
}
PriorityQueue<Node> pq = new PriorityQueue<Node>((o1, o2) -> o1.cost - o2.cost);
if (board[0][1] != 1) {
pq.add(new Node(0, 1, 1, 100));
arr[0][1] = 100;
}
if (board[1][0] != 1) {
pq.add(new Node(1, 0, 0, 100));
arr[1][0] = 100;
}
while (!pq.isEmpty()) {
Node node = pq.poll();
if (board[node.x][node.y] == 1)
continue;
if (node.x == N - 1 && node.y == N - 1) {
answer = node.cost;
break;
}
for (int i = 0; i < 4; i++) {
int x = node.x + d[i][0];
int y = node.y + d[i][1];
int cost = node.cost + (node.direct == i ? 100 : 600);
if (x >= 0 && x < N && y >= 0 && y < N && (arr[x][y] >= cost || !visited[x][y][i])) {
pq.add(new Node(x, y, i, cost));
arr[x][y] = cost;
visited[x][y][i] = true;
}
}
}
return answer;
}
static class Node {
int x, y, direct, cost;
public Node(int x, int y, int direct, int cost) {
this.x = x;
this.y = y;
this.direct = direct;
this.cost = cost;
}
}
}
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
미로탈출 (0) | 2022.05.06 |
---|---|
보석 쇼핑 (0) | 2022.03.04 |
2 x n 타일링 (0) | 2021.12.29 |
124 나라의 숫자 (0) | 2021.12.28 |
구명보트 (0) | 2021.11.23 |