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

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

프로그래머스

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 카드 짝 맞추기

 

난이도: LEVEL3

알고리즘 유형: 완전탐색 + 구현 

풀이 설명

완전 탐색을 사용하는 빡 구현 문제이다. 

board 크기는 4 * 4 크기의 배열의 작은 2차원 배열

카드의 최대 종류는 1 ~ 6 이다. 

 

완전탐색을 사용하면 최대 6! * 2^6 이다.

6! 카드의 종류를 서로 다른 순서에 방문하는 경우의 수이고 2^6는 각 카드는 2개인데 어떤 카드를 먼저 방문해서 뒤집는지에 해당한다. 

 

즉 종류가 2개면

 

카드 방문 순서는 2개 (2!)

1 → 2

2 → 1 

 

각 카드의 경우의수 (2^2)

1의 방문 순서 2개

2의 방문 순서 2개

결과적으로 2! * 2^n 경우의 수가 나온다.

 

완전 탐색인 문제는 이렇게 데이터 셋을 확인하고 완전 탐색이 가능한지 먼저 파악을 해야한다. 

만약 완탐으로 불가능한 시간 복잡도가 나온다면 다른 알고리즘을 고려해야 할 가능성이 높다.  

 

최악의 경우 6! * 2^6인데 충분히 가능한 시간 복잡도 

→ 물론 여기서 4*4 배열의 탐색이 추가적으로 들어가지만 배열 크기가 작아서 큰 영향이 없다. 

 

카드의 순서를 백트래킹을 통해서 탐색하고 

2개의 카드를 서로 다른 순서로 방문하는 방식으로 또 백트래킹을 나눈다. 

if(depth == sequence.length){
    answer = Math.min(answer, count);
    return;
}

for(int i = 1; i <= 6; i++){
    if(!memo[i] || visited[i]) continue;
    visited[i] = true;
    sequence[depth] = i;

    // 순서 다르게 이동하기1
    int use1 = game(record[i][0], record[i][1], record[i][2], record[i][3], x, y);

    backTracking(depth + 1, record[i][2], record[i][3], count + use1);
    // 백트래킹 이후 다시 복구 
    boards[record[i][0]][record[i][1]] = i;
    boards[record[i][2]][record[i][3]] = i;

    // 순서 다르게 이동하기1
    int use2 = game(record[i][2], record[i][3], record[i][0], record[i][1], x, y);

    backTracking(depth + 1, record[i][0], record[i][1], count + use2);
    // 백트래킹 이후 다시 복구 
    boards[record[i][0]][record[i][1]] = i;
    boards[record[i][2]][record[i][3]] = i;

    visited[i] = false;
}

 

방문 방법은 BFS를 통해서 접근하였다.

핵심은 현재 좌표까지 최소 1을 이동했을 때
현재 좌표에서 다른 좌표까지 키 조작을 1만 소비해서 하는 이동은 1칸을 이동하거나 해당 방향으로 카드를 만날 때 까지거나 아님 board 끝까지 가는 경우이다. 

만약 1칸씩 이동하면서 큐에 추가하고 최단거리를 갱신하면 잘못된 결과가 나온다. 

 

필수 작업 

카드를 방문하고 삭제 & 재귀 함수가 끝나고 다시 돌아오면 복구

카드를 방문하고 enter를 누르자 (조작 횟수 default + 2)

boards[sx][sy] = 0;
boards[ex][ey] = 0; 

backTracking(depth + 1, record[i][0], record[i][1], count + use2);
// 백트래킹 이후 다시 복구 
boards[record[i][0]][record[i][1]] = i;
boards[record[i][2]][record[i][3]] = i;

 

정답 코드

import java.util.*;
class Solution {
    static int answer = Integer.MAX_VALUE;
    static boolean [] memo = new boolean [7]; // 0 ~ 6 이하의 숫자 
    static boolean [] visited = new boolean [7];
    static int [][] record = new int [7][4];
    static int [] sequence;
    static int [][] boards;
    static int size;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static final int MAX = 16;
    public int solution(int[][] board, int r, int c) {
        boards = board; 
        size = board.length;
        init();
        backTracking(0, r, c, 0);
        return answer;
    }
    public static int game(int sx, int sy, int ex, int ey, int cur_x, int cur_y){
        int num = boards[sx][sy];
        int sum = 0;
        int [][] map = new int [size][size];
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                map[i][j] = MAX;
            }
        }
        map[cur_x][cur_y] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int [] {cur_x, cur_y});
        while(!q.isEmpty()){
            int [] cur = q.poll();
            for(int i = 0; i < 4; i++){  // 1칸 이동 or 같은 방향으로 쭉 이동 
                int x = cur[0] + arx[i];
                int y = cur[1] + ary[i];
                if(!validation(x, y)) continue;
                // 1칸 이동 
                if(map[x][y] > map[cur[0]][cur[1]] + 1){
                    map[x][y] = map[cur[0]][cur[1]] + 1;
                    q.add(new int [] {x, y});
                }
                
                // 카드라면 멈춘다. 
                if(boards[x][y] != 0 ) continue; 
                
                // 카드가 아니라면 카드 or 마지막 까지 이동하기 
                boolean flag = false; // 카드로 끝나면 index 계산 필요 x
                while(true){
                    x += arx[i];
                    y += ary[i];
                    if(!validation(x, y)) break;
                    if(boards[x][y] != 0){
                        flag = true;
                        break;
                    }
                }
                if(!flag){
                    x -= arx[i];
                    y -= ary[i];
                }
                if(map[x][y] > map[cur[0]][cur[1]] + 1){
                    map[x][y] = map[cur[0]][cur[1]] + 1;
                    q.add(new int []{x, y});
                }
            }
        }
        sum += map[sx][sy];
        // 다시 map 초기화 
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                map[i][j] = MAX;
            }
        }
        map[sx][sy] = 0;
        q.add(new int [] {sx, sy});
        while(!q.isEmpty()){
            int [] cur = q.poll();
            for(int i = 0; i < 4; i++){  // 1칸 이동 or 같은 방향으로 쭉 이동 
                int x = cur[0] + arx[i];
                int y = cur[1] + ary[i];
                if(!validation(x, y)) continue;
                // 1칸 이동 
                if(map[x][y] > map[cur[0]][cur[1]] + 1){
                    map[x][y] = map[cur[0]][cur[1]] + 1;
                    q.add(new int [] {x, y});
                }
                
                // 카드라면 멈춘다. 
                if(boards[x][y] != 0 ) continue; 
                
                // 카드가 아니라면 카드 or 마지막 까지 이동하기 
                boolean flag = false; // 카드로 끝나면 index 계산 필요 x
                while(true){
                    x += arx[i];
                    y += ary[i];
                    if(!validation(x, y)) break;
                    if(boards[x][y] != 0){
                        flag = true;
                        break;
                    }
                }
                if(!flag){
                    x -= arx[i];
                    y -= ary[i];
                }
                if(map[x][y] > map[cur[0]][cur[1]] + 1){
                    map[x][y] = map[cur[0]][cur[1]] + 1;
                    q.add(new int []{x, y});
                }
            }
        }
        // 카드 삭제
        boards[sx][sy] = 0;
        boards[ex][ey] = 0; 
        sum += map[ex][ey];
        sum += 2; // enter를 누른다. 
        return sum;
    }
    // ArrayOutOfIndex 검사 
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < size && ny < size) return true;
        return false;
    }    

    public static void backTracking(int depth, int x, int y, int count){
        if(depth == sequence.length){
            answer = Math.min(answer, count);
            return;
        }
        
        for(int i = 1; i <= 6; i++){
            if(!memo[i] || visited[i]) continue;
            visited[i] = true;
            sequence[depth] = i;
            
            // 순서 다르게 이동하기1
            int use1 = game(record[i][0], record[i][1], record[i][2], record[i][3], x, y);
            
            backTracking(depth + 1, record[i][2], record[i][3], count + use1);
            // 백트래킹 이후 다시 복구 
            boards[record[i][0]][record[i][1]] = i;
            boards[record[i][2]][record[i][3]] = i;
            
            // 순서 다르게 이동하기1
            int use2 = game(record[i][2], record[i][3], record[i][0], record[i][1], x, y);
            
            backTracking(depth + 1, record[i][0], record[i][1], count + use2);
            // 백트래킹 이후 다시 복구 
            boards[record[i][0]][record[i][1]] = i;
            boards[record[i][2]][record[i][3]] = i;
            
            visited[i] = false;
        }
    }
    // 1 ~ 6 숫자인 카드들의 존재를 boolean 배열 memo에 저장 
    // 1 ~ 6 숫자의 카드 좌표를 record 배열에 저장 
    // 1 ~ 6 숫자의 개수를 count 해서 sequence 배열 초기화 (백트래킹 용도)
    public static void init(){
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                int num = boards[i][j];
                if(num == 0) continue;
                if(!memo[num]){
                    memo[num] = true;
                    record[num][0] = i;
                    record[num][1] = j;
                }
                else{
                    record[num][2] = i;
                    record[num][3] = j;
                }
            }
        }
        int count = 0;
        for(int i = 1; i <= 6; i++){
            if(memo[i]) count++;
        }
        sequence = new int [count];
    }
}