2021 - 카드 짝 맞추기

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

[ 문제풀이 ]

주어진 카드들을 방문할 수 있는 모든 경우의 수를 탐색해주면 되는 완전 탐색 문제이다. 별다른 알고리즘을 요구하는 것은 아니지만 구현하는데 생각보다 까다로워서 많은 시간이 걸렸다.

​모든 경우의 수를 만들기 위해선 2가지를 고려해줘야 한다.

​첫 번째는 몇 번째 카드를 먼저 제거할 것인지에 대한 순서이다.

​예를 들어 카드가 1, 2, 3, 총 3개가 있다면 3개의 카드를 방문할 수 있는 경우의 수는 3!이다.

1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1

이는 백트래킹 기반의 순열 구하는 알고리즘으로 간단하게 구할 수 있다.

​두 번째로 고려해야 할 것은 각 카드의 어떤 카드를 먼저 제거할 것인지이다. 각 카드는 쌍으로 존재하기 때문에 카드마다 2가지의 경우의 수가 발생한다.

1(2)-1(1), 1(1)-1(2)

이 또한 마찬가지로 백트래킹을 이용해서 구현해주면 된다. 또한, 쉽게 관리해주기 위해 카드가 주어지면 카드 한 개에 10을 곱해줬다.

1-10, 10-1

탐색할 순서를 정해줬다면 bfs + dp를 통해 최소 이동 횟수를 구해주면 된다.

import java.util.*;

class Solution {
	boolean[] visit;
	int answer;
	List<Integer> cardList, pick1, pick2;
	Queue<Node> q;
	
	int[][] dp, dir = {{-1,0}, {0,1}, {1,0}, {0,-1}};
	
	class Node {
		int r, c, d, move;
		int[][] board;

		public Node (int r, int c, int d, int move) {
			this.r = r;
			this.c = c;
			this.d = d;
			this.move = move;
			board = new int[4][4];
		}
	}

	public int solution(int[][] board, int r, int c) {
		answer = (int)1e9;
		
		cardList = new ArrayList<>();
		boolean[] check = new boolean[7];
		
		//1~6까지의 카드를 cardList에 담아줌
		//각 카드는 쌍으로 존재하기 때문에 이를 구별해주기 위해 한개는 10을 곱해줌
		//1-10, 2-20, 3-30, 4-40, 5-50, 6-60
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				//방문하지 않은 카드라면
				if (board[i][j] != 0 && !check[board[i][j]]) {
					check[board[i][j]] = true;
					cardList.add(board[i][j]);
					board[i][j] *= 10;
				}
			}
		}
		
		q = new LinkedList<>(); pick1 = new ArrayList<>(); pick2 = new ArrayList<>();
		dp = new int[4][4];
		visit = new boolean[cardList.size()];
		
		pick1(board, r, c);

		return answer;
	}

	//제거할 카드의 순서를 정함
	//ex) 3개의 카드가 존재한다면
	//1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1
	public void pick1(int[][] board, int r, int c) {
		if (pick1.size() == cardList.size()) {
			pick2(board, r, c, 0);
			return;
		}

		for (int i = 0; i < cardList.size(); ++i) {
			if (visit[i]) continue;

			visit[i] = true;
			pick1.add(cardList.get(i));
			pick1(board, r, c);
			pick1.remove(pick1.size() - 1);
			visit[i] = false;
		}
	}

	//각 카드는 쌍으로 존재하기 때문에 어떤 카드부터 탐색할 것인지
	//이를 구분하기 위해 카드 한쪽에 10을 곱해줌
	//ex) 1-10, 10-1 순서대로 카드마다 2개의 경우의 수가 존재
	public void pick2(int[][] board, int r, int c, int idx) {
		//탐색할 카드의 모든 순서가 정해졌다면 탐색 시작
		if (idx == pick1.size()) {
			Node node = new Node(r, c, -1, 0);
			for (int i = 0; i < 4; ++i) {
				for (int j = 0; j < 4; ++j) {
					node.board[i][j] = board[i][j];
				}
			}
			
			simulation(0, node);
			return;
		}

		//1-10 순서
		pick2.add(pick1.get(idx));
		pick2.add(pick1.get(idx) * 10);
		pick2(board, r, c, idx + 1);
		pick2.remove(pick2.size() - 1);
		pick2.remove(pick2.size() - 1);

		//10-1 순서
		pick2.add(pick1.get(idx) * 10);
		pick2.add(pick1.get(idx));
		pick2(board, r, c, idx + 1);
		pick2.remove(pick2.size() - 1);
		pick2.remove(pick2.size() - 1);
	}
	
	public void simulation(int idx, Node node) {
		//모든 순서를 탐색 완료했다면 최소 움직임 횟수 갱신
		if (idx >= pick2.size()) {
			answer = Math.min(answer, node.move);
			return;
		}

		q.clear();
		q.offer(node);

		Node n = null;
		
		//중복방문을 방지하기 위해
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				dp[i][j] = (int)1e9;
			}
		}

		while (!q.isEmpty()) {
			n = q.poll();

			//현재 움직임 횟수가 정답 이상이면 더이상 탐색할 필요 없음
			if (n.move >= answer) return;

			//현재 순서인 카드를 방문했다면
			if (n.board[n.r][n.c] == pick2.get(idx)) {
				break;
			}

			//이전에 방문한 움직임 횟수보다 현재 움직임 횟수가 크다면 더이상 탐색할 필요 없음
			if (dp[n.r][n.c] <= n.move) continue;
			dp[n.r][n.c] = n.move;

			//0~4 : 한칸이동, 5~8 : Ctrl 이동
			for (int i = 0; i < 8; ++i) {
				if (n.d == i) continue; //이전에 진행한 방향이라면 x

				q.offer(move(i, n));
			}
		}

		n.move++; //Enter
		
		int y = n.r, x = n.c; //카드를 제거하기 위해 좌표를 저장

		q.clear();
		q.offer(n);
		
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				dp[i][j] = (int)1e9;
			}
		}
		
		while (!q.isEmpty()) {
			n = q.poll();
			
			//현재 움직임 횟수가 정답 이상이면 더이상 탐색할 필요 없음
			if (n.move >= answer) return;
			
			//현재 순서인 카드를 방문했다면
			if (n.board[n.r][n.c] == pick2.get(idx + 1)) {
				break;
			}

			//이전에 방문한 움직임 횟수보다 현재 움직임 횟수가 크다면 더이상 탐색할 필요 없음
			if (dp[n.r][n.c] <= n.move) continue;
			dp[n.r][n.c] = n.move;
			
			//0~4 : 한칸이동, 5~8 : Ctrl 이동
			for (int i = 0; i < 8; ++i) {
				if (n.d == i) continue; //이전에 진행한 방향이라면 x

				q.offer(move(i, n));
			}
		}

		n.move++; //Enter
		n.board[y][x] = 0; n.board[n.r][n.c] = 0; //카드를 제거
		
		simulation(idx + 2, n);
	}

	public Node move(int d, Node node) {
		//새로운 Node 생성
		Node n = new Node(node.r, node.c, d, node.move + 1);
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				n.board[i][j] = node.board[i][j];
			}
		}

		//Ctrl을 사용하여 끝까지 이동
		if (d >= 4) {
			d -= 4;
			
			while (true) {
				int nr = n.r + dir[d][0];
				int nc = n.c + dir[d][1];

				if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4) break;

				n.r = nr;
				n.c = nc;

				if (n.board[nr][nc] != 0) {
					break;
				}
			}
		} 
		//한칸이동
		else {
			int nr = n.r + dir[d][0];
			int nc = n.c + dir[d][1];
			
			if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4) return n;
			
			n.r = nr;
			n.c = nc;
		}
		
		return n;
	}
}