[프로그래머스] 카드 짝 맞추기 (Java)

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

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

import java.util.*;

class Solution {
	static int[][] pairs = new int[7][4];
	static int answer = Integer.MAX_VALUE;
	static int limit = 0;
	static ArrayList<Integer> numbers = new ArrayList<>();
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public int solution(int[][] board, int r, int c) {
		for (int i = 0; i < 7; i++) {
			Arrays.fill(pairs[i], -1);
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (board[i][j] != 0) {
					int num = board[i][j];
					if (pairs[num][0] == -1) {
						pairs[num][0] = i;
						pairs[num][1] = j;
						limit++;
						numbers.add(num);
					} else {
						pairs[num][2] = i;
						pairs[num][3] = j;
					}
				}
			}
		}
		perm(r, c, board, 0, 0, new boolean[7]);
		return answer;
	}

	public void perm(int r, int c, int[][] board, int cnt, int sum, boolean[] visited) {
		if (sum > answer)
			return;
		if (cnt == limit) {
			answer = Math.min(answer, sum);
			return;
		}
		//System.out.println(r + " " + c);
		for (int i = 0; i < numbers.size(); i++) {
			int picked = numbers.get(i);
			if (visited[picked])
				continue; // 뒤집을 카드를 정함
			visited[picked] = true;
			int dist1 = bfs(r, c, pairs[picked][0], pairs[picked][1], picked, board)
					+ bfs(pairs[picked][0], pairs[picked][1], pairs[picked][2], pairs[picked][3], picked, board);
			board[pairs[picked][0]][pairs[picked][1]]=0;
            board[pairs[picked][2]][pairs[picked][3]]=0;
			perm(pairs[picked][2], pairs[picked][3], board, cnt + 1, sum + dist1 + 2, visited);
            board[pairs[picked][0]][pairs[picked][1]]=picked;
            board[pairs[picked][2]][pairs[picked][3]]=picked;
			int dist2 = bfs(r, c, pairs[picked][2], pairs[picked][3], picked, board)
					+ bfs(pairs[picked][2], pairs[picked][3], pairs[picked][0], pairs[picked][1], picked, board);
			board[pairs[picked][0]][pairs[picked][1]]=0;
            board[pairs[picked][2]][pairs[picked][3]]=0;
			perm(pairs[picked][0], pairs[picked][1], board, cnt + 1, sum + dist2 + 2, visited);
            board[pairs[picked][0]][pairs[picked][1]]=picked;
            board[pairs[picked][2]][pairs[picked][3]]=picked;
			visited[picked] = false;
		}
	}

	private int bfs(int start_r, int start_c, int dest_r, int dest_c, int num, int[][] board) { // start~dest 까지 비용 계산
		int r, c, cnt, nr, nc;
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visited = new boolean[4][4];
		q.add(new int[] { start_r, start_c, 0 });
		visited[start_r][start_c] = true;
		while (!q.isEmpty()) {
			int[] curr = q.poll();
			r = curr[0];
			c = curr[1];
			cnt = curr[2];
			if (r == dest_r && c == dest_c) {
				return cnt;
			}
			for (int i = 0; i < 4; i++) {
				nr = r + dr[i];
				nc = c + dc[i];
				if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4)
					continue;
				if (!visited[nr][nc]) {
					q.add(new int[] { nr, nc, cnt + 1 });
					visited[nr][nc] = true;
				}
			}
			for (int i = 0; i < 4; i++) {
				nr = r;
				nc = c;
				while (true) {
					nr += dr[i];
					nc += dc[i];
					if (nr < 0 || nc < 0 || nr >= 4 || nc >= 4) {
						nr -= dr[i];
						nc -= dc[i];
						break;
					}
					if (board[nr][nc] != 0) {
						break;
					}
				}
				if (!visited[nr][nc]) {
					q.add(new int[] { nr, nc, cnt + 1 });
					visited[nr][nc] = true;
				}
			}
		}
		return -1;
	}
}

https://yjyoon-dev.github.io/kakao/2021/01/29/kakao-paircard/

 

완전탐색+시뮬레이션 문제

 

뒤집을 카드의 순서를 정하고=>뒤집을 카드를 정했으면 1번째 카드 먼저 뒤집을 것인지, 2번째 카드 먼저 뒤집을 것인지 나눈다. (perm 함수)

 

이후 BFS 함수에서 start 카드에서 dest 카드까지 갈 수 있는 최소 거리를 구해준다.

비용 계산은 현재 놓인 카드 위치~(1 또는 2 번째 카드 위치)~(2 또는 1번째 카드 위치)를 더한 값에다, +2를 더해준다. (엔터 2번)