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

문제 설명

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

board는 4 x 4 크기의 2차원 배열입니다.
board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
0은 카드가 제거된 빈 칸을 나타냅니다.
1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
r은 커서의 최초 세로(행) 위치를 의미합니다.
c는 커서의 최초 가로(열) 위치를 의미합니다.
r과 c는 0 이상 3 이하인 정수입니다.
게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.

Code

import java.util.*;
class Solution {
    private Map<Integer, List<Integer>> cardsMap;
	private List<Integer> cardsList;
	private int minStep;
    public int solution(int[][] board, int r, int c) {
        minStep = Integer.MAX_VALUE;
		
		init(board);
		dfs(r, c, board, new boolean[cardsList.size()], 0, 0);
		
		return minStep;
    }
    
    public void init(int[][] board) {
		int m=board.length, n=board[0].length;
		cardsMap = new HashMap<>();
		cardsList = new ArrayList<>();
		for(int i=0 ; i<m ; i++) {
			for(int j=0 ; j<n ; j++) {
				if(board[i][j]==0) continue;
				if(!cardsList.contains(board[i][j])) {
					cardsList.add(board[i][j]);
					cardsMap.put(board[i][j], new ArrayList<>());
				}
				cardsMap.get(board[i][j]).add(i);
				cardsMap.get(board[i][j]).add(j);
			}
		}
		return;
	}
    
    public void dfs(int i, int j, int[][] board, boolean[] visit, int cnt, int step) {

		if(cnt==visit.length) {
			minStep = Math.min(minStep, step);
			return;
		}
		for(int x=0 ; x<visit.length ; x++) {
			if(visit[x]) continue;
			visit[x] = true;
			
			int card = cardsList.get(x);
			List<Integer> p = cardsMap.get(card);
			int i1=p.get(0), j1=p.get(1), i2=p.get(2), j2=p.get(3); 
			int s11 = getDistance(i, j, i1, j1, (i1-i>0?1:-1), (j1-j>0?1:-1), board, 0);
			int s12 = getDistance(i1, j1, i2, j2, (i2-i1>0?1:-1), (j2-j1>0?1:-1), board, 0);
			int s21 = getDistance(i, j, i2, j2, (i2-i>0?1:-1), (j2-j>0?1:-1), board, 0);
			int s22 = getDistance(i2, j2, i1, j1, (i1-i2>0?1:-1), (j1-j2>0?1:-1), board, 0);
			board[i1][j1] = 0;
			board[i2][j2] = 0;
			
			dfs(i2, j2, board, visit, cnt+1, step+s11+s12+2);
			dfs(i1, j1, board, visit, cnt+1, step+s21+s22+2);
			
			board[i1][j1] = card;
			board[i2][j2] = card;
			visit[x] = false;
		}
		return;
	}
    
    public int getDistance(int si, int sj, int ei, int ej, int iPlus, int jPlus, int[][] board, int step) {
		
		if(si<0 || si>=4 || sj<0 || sj>=4) return 20;
		if(si==ei && sj==ej) return step;

		
		int i=si+iPlus, j=sj+jPlus;
		
		int w = Math.min(getDistance(i, sj, ei, ej, iPlus, jPlus, board, step+1), getDistance(si, j, ei, ej, iPlus, jPlus, board, step+1));
		
		while(i>0 && i<3 && board[i][sj]==0) {
			i+=iPlus;
		}
		int wi = getDistance(i, sj, ei, ej, iPlus, jPlus, board, step+1);
		while(j>0 && j<3 && board[si][j]==0) {
			j+=jPlus;
		}
		int wj = getDistance(si, j, ei, ej, iPlus, jPlus, board, step+1);
		return Math.min(w, Math.min(wi, wj));
	}
    
}