[Programmers] 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기

note.JW·2021년 4월 1일
0

Algorithm

목록 보기
10/10
post-thumbnail

2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기

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

이렇게 큰 두 개의 알고리즘을 풀었다.
다익스트라 응용하는 부분에서 시간을 좀 허비했다. 커서로 한 칸씩 이동하는게 더 가까울 때가 있다는 점을 생각하지 못했었다.

profile
🎆우주란 무엇일까🎆

1개의 댓글

comment-user-thumbnail
2021년 4월 16일

좋은 정보 감사합니다!

답글 달기