using Java 11
import java.util.*;
public class Solution {
public static int[] dr = {1, 0, -1, 0};
public static int[] dc = {0, -1, 0, 1};
static class Node implements Comparable<Node>{
int dist;
int r;
int c;
public Node(int dist, int r, int c) {
this.dist = dist;
this.r = r;
this.c = c;
}
public Node(int r, int c) {
this.r = r;
this.c = c;
}
@Override
public int compareTo(Node o) {
return this.dist - o.dist;
}
}
public static boolean isValid(int r, int c) {
if(r < 0 || c < 0 || r > 3 || c > 3) {
return false;
}
return true;
}
public static boolean isZero(int[][] board) {
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
if(board[i][j] != 0) return false;
return true;
}
public static int getDist(int[][] board, int r, int c, int toR, int toC) {
int[][] dist = new int[4][4];
for(int i = 0; i < 4; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(0, r, c));
dist[r][c] = 0;
int curD = 0;
while(!pq.isEmpty()) {
Node curNode = pq.poll();
curD = curNode.dist;
if(dist[curNode.r][curNode.c] < curNode.dist) continue;
if(curNode.r == toR && curNode.c == toC) return curD;
for(int i = 0; i < 4; i++) {
int count = 0;
int nr = curNode.r;
int nc = curNode.c;
while(isValid(nr + dr[i],nc + dc[i])) {
count++;
nr += dr[i]; nc += dc[i];
//카드 만났을때;
if(board[nr][nc] != 0) break;
if(dist[nr][nc] > curD + count) {
dist[nr][nc] = curD + count;
pq.add(new Node(curD + count, nr, nc));
}
}
//(ctrl) + 방향키
if(dist[nr][nc] > curD + 1) {
dist[nr][nc] = curD + 1;
pq.add(new Node(curD+1, nr, nc));
}
}
}
return curD;
}
public static int dfs(int[][] board, int r, int c) {
int min = Integer.MAX_VALUE;
if(isZero(board)) return 0;
for(int cardNum = 1; cardNum < 7; cardNum++) {
ArrayList<Node> cardList = new ArrayList<>();
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
if(board[i][j] == cardNum) {
cardList.add(new Node(i, j));
}
}
}
if(cardList.isEmpty()) continue;
//최소 방향키로 이동 (case1: pair1 > pair2, case2: pair2 > pair1 찾는 경우)
int case1 = getDist(board, r, c, cardList.get(0).r, cardList.get(0).c)
+ getDist(board,cardList.get(0).r, cardList.get(0).c, cardList.get(1).r, cardList.get(1).c)+2;
int case2 = getDist(board, r, c, cardList.get(1).r, cardList.get(1).c)
+ getDist(board,cardList.get(1).r, cardList.get(1).c, cardList.get(0).r, cardList.get(0).c)+2;
//뒤집기
board[cardList.get(0).r][cardList.get(0).c] = 0;
board[cardList.get(1).r][cardList.get(1).c] = 0;
//다음 카드
min = Math.min(min, Math.min(case1 + dfs(board, cardList.get(1).r, cardList.get(1).c),
case2+ dfs(board, cardList.get(0).r, cardList.get(0).c)));
board[cardList.get(0).r][cardList.get(0).c] = cardNum;
board[cardList.get(1).r][cardList.get(1).c] = cardNum;
}
return min;
}
public static int solution(int[][] board, int r, int c) {
int answer = dfs(board, r, c);
return answer;
}
}
📍 단계 나누기
1. 카드 뒤집는 순서 결정 : dfs/backtracking
2. 커서 이동 count : dijkstra
이렇게 큰 두 개의 알고리즘을 풀었다.
다익스트라 응용하는 부분에서 시간을 좀 허비했다. 커서로 한 칸씩 이동하는게 더 가까울 때가 있다는 점을 생각하지 못했었다.
좋은 정보 감사합니다!