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

문제

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

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

문제해결방법

먼저, 카드에서 카드로 가는 최소 명령의 수를 찾아내는 함수를 만들었다.

그리고 카드의 종류를 기준으로 어떤 순서로 카드를 뒤집을 지 조합을 짠다.

카드 종류를 뒤집을 때 어떤 카드부터 먼저 뒤집을 지 정하며 명령의 개수를 센다.

모든 순서 조합으로 카드를 뒤집었을 때 가장 적은 명령을 사용한 경우의 명령 수를 반환한다.

코드

package Programmers;
 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
 
public class Solution_카드짝맞추기 {
    
    public static int min = Integer.MAX_VALUE, count = 0;
    public static boolean[] v = new boolean[7];
    public static List<int[]>[] cards = new List[7];
    public static int[][] dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    
    public static int calRoute(int[][] board, int[] card1, int[] card2, int card) {
        int[][] distance = new int[board.length][board.length];
        for(int i=0; i<distance.length; i++) {
            for(int j=0; j<distance[i].length; j++) distance[i][j] = Integer.MAX_VALUE;
        }
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.add(card1);
        distance[card1[0]][card1[1]] = 0;
        loop:while(!q.isEmpty()) {
            int[] cur = q.poll();
            int curDis = distance[cur[0]][cur[1]];
            for(int d=0; d<dir.length; d++) {
                int xx = cur[0]+dir[d][0];
                int yy = cur[1]+dir[d][1];
                while(xx>=0 && xx<board.length && yy>=0 && yy<board.length && board[xx][yy]==0) {
                    xx+=dir[d][0];
                    yy+=dir[d][1];
                }
                if(xx<0 || xx>=board.length || yy<0 || yy>=board.length) {
                    xx-=dir[d][0];
                    yy-=dir[d][1];
                }
                if(distance[xx][yy]>curDis+1) {
                    distance[xx][yy]=curDis+1;
                    q.add(new int[] {xx, yy});
                    if(xx==card2[0] && yy==card2[1]) break loop;
                }
 
                xx = cur[0]+dir[d][0];
                yy = cur[1]+dir[d][1];
                if(xx>=0 && xx<board.length && yy>=0 && yy<board.length && distance[xx][yy]>curDis+1) {
                    distance[xx][yy]=curDis+1;
                    q.add(new int[] {xx, yy});
                    if(xx==card2[0] && yy==card2[1]) break loop;
                }
            }
        }
        return distance[card2[0]][card2[1]];
    }
    
    public static void comb(int[][] board, int[] pos, int command, int c) {
        if(min<command) return;
        if(count<=c) {
            if(min>command) min = command;
            return;
        }
        for(int i=1; i<cards.length; i++) {
            if(v[i]) {
                v[i]=false;
                int[] card1 = cards[i].get(0);
                int posToCard1 = calRoute(board, pos, card1, i);
                int[] card2 = cards[i].get(1);
                int posToCard2 = calRoute(board, pos, card2, i);
                int c1ToC2 = calRoute(board, card1, card2, i);
                int c2ToC1 = calRoute(board, card2, card1, i);
                board[card1[0]][card1[1]] = 0;
                board[card2[0]][card2[1]] = 0;
                comb(board, card2, command+posToCard1+c1ToC2+2, c+1);
                comb(board, card1, command+posToCard2+c2ToC1+2, c+1);
                board[card1[0]][card1[1]] = i;
                board[card2[0]][card2[1]] = i;
                v[i]=true;
            }
        }
    }
    
    public static int solution(int[][] board, int r, int c) {
        for(int i=0; i<cards.length; i++) cards[i] = new ArrayList<int[]>();
        int answer = 0;
        count = 0;
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if(board[i][j]!=0) {
                    v[board[i][j]] = true;
                    count++;
                    cards[board[i][j]].add(new int[] {i, j});
                }
            }
        }
        count/=2;
        comb(board, new int[] {r, c}, 0, 0);
        answer = min;
        return answer;
    }
    
    public static void main(String[] args) {
        int[][] board = {{3,0,0,2}, {0,0,1,0}, {0,1,0,0}, {2,0,0,3}};
        int r = 0;
        int c = 1;
        System.out.println(solution(board, r, c));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.