[2021 KAKAO BLIND RECRUITMENT] 카드 짝 맞추기

2021 KAKAO BLIND RECRUITMENT 카드 짝 맞추기

유형

• 순열
• BFS

문제 풀이에 대한 감을 잡기 위해, 카카오 공식 문제 해설을 먼저 참고하였다.

코드

import java.util.*;

class Solution {

    static class Point {
        int x;
        int y;
        int count;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }

    }

    static ArrayList<int[]> perms;
    static ArrayList<Point[]> cardRemovePath;
    static HashMap<Integer, ArrayList<Point>> cardsPosition;

    public int solution(int[][] board, int r, int c) {

        // 카드 종류별로 Map에 위치 저장
        cardsPosition = new HashMap<>();
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                if(board[i][j] != 0) {
                    int cardNum = board[i][j];
                    ArrayList<Point> value = cardsPosition.getOrDefault(cardNum, new ArrayList<>());
                    value.add(new Point(i, j));
                    cardsPosition.put(cardNum, value);
                }
            }
        }

        int numOfCard = cardsPosition.keySet().size();
        int[] cards = new int[numOfCard];
        Object[] array = cardsPosition.keySet().toArray();
        for(int i = 0; i < numOfCard; i++) {
            cards[i] = (int) array[i];
        }

        //카드 중 어떤 카드부터 제거해 나갈지 순열을 생성한다.
        //각 카드는 종류별로 2장씩임을 주의하여, 순열에 각 카드의 위치를 매핑시킨다.
        perms = new ArrayList<>();
        cardRemovePath = new ArrayList<>();
        permutation(cards, new int[numOfCard], new boolean[numOfCard], 0, numOfCard, numOfCard);

        // 카드를 제거하는 모든 순서에 대해서 각각 카드를 제거해 보고, 그중 키 조작 횟수가 가장 적은 방법을 찾는다.
        int min = cardRemovePath.stream()
                .mapToInt(path -> removeCard(board, path, r, c))
                .min()
                .getAsInt();

        min += 2 * numOfCard;

        return min;

    }

    private static int removeCard(int[][] board, Point[] path, int r, int c) {
        int[][] clone = new int[4][4];
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                clone[i][j] = board[i][j];
            }
        }

        int count = 0;
        Point origin = new Point(r, c);
        for(Point next: path) {
            count += bfs(clone, origin, next);
            clone[origin.x][origin.y] = 0;
            clone[next.x][next.y] = 0;
            origin = next;
        }
        return count;
    }

    static int[] dr = {-1, 1, 0, 0};   //상, 하, 좌, 우
    static int[] dc = {0, 0, -1, 1};

    // 최소 조작 횟수는 BFS 탐색을 이용하여 최단거리를 구한다.
    private static int bfs(int[][] board, Point origin, Point dest) {

        Queue<Point> q = new LinkedList<>();
        boolean[][] visited = new boolean[4][4];

        q.offer(origin);
        visited[origin.x][origin.y] = true;

        while(!q.isEmpty()) {
            Point next = q.poll();
            if(next.x == dest.x && next.y == dest.y) {
                return next.count;
            }
            // 상하좌우
            for(int i = 0; i < 4; i++) {
                int nr = next.x + dr[i];
                int nc = next.y + dc[i];
                if(nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {
                    if(visited[nr][nc] == false) {
                        visited[nr][nc] = true;
                        q.offer(new Point(nr, nc, next.count + 1));
                    }
                }
            }
            // CTRL + 상하좌우
            for(int i = 0; i < 4; i++) {
                int nr = next.x + dr[i];
                int nc = next.y + dc[i];
                boolean find = false;
                while (nr >= 0 && nr < 4 && nc >= 0 && nc < 4) {
                    if (board[nr][nc] != 0) {
                        find = true;
                        break;
                    }
                    nr += dr[i];
                    nc += dc[i];
                }
                if (find == false) {
                    nr -= dr[i];
                    nc -= dc[i];
                }
                if (!(nr == next.x && nc == next.y) && visited[nr][nc] == false) {
                    visited[nr][nc] = true;
                    q.offer(new Point(nr, nc, next.count + 1));
                }
            }
        }
        return 0;
    }

    //순열 nPr
    private static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
        if(depth == r) {
            perms.add(makePerm(output, r));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(visited[i] != true) {
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    // 배열 출력
    private static int[] makePerm(int[] arr, int r) {
        int[] perm = new int[r];
        for (int i = 0; i < r; i++) {
            perm[i] = arr[i];
        }

        Point[] path = new Point[2 * r];
        makeCardRemovePath(perm, path, 0);

        return perm;
    }

    private static void makeCardRemovePath(int[] perm, Point[] path, int depth) {
        path[2 * depth] = cardsPosition.get(perm[depth]).get(0);
        path[2 * depth + 1] = cardsPosition.get(perm[depth]).get(1);
        if(depth == perm.length - 1) {
            cardRemovePath.add(path);
            Point[] clone = path.clone();
            clone[2 * depth] = cardsPosition.get(perm[depth]).get(1);
            clone[2 * depth + 1] = cardsPosition.get(perm[depth]).get(0);
            cardRemovePath.add(clone);
        } else {
            makeCardRemovePath(perm, path.clone(), depth + 1);
            Point[] clone = path.clone();
            clone[2 * depth] = cardsPosition.get(perm[depth]).get(1);
            clone[2 * depth + 1] = cardsPosition.get(perm[depth]).get(0);
            makeCardRemovePath(perm, clone.clone(), depth + 1);
        }
    }

}

참고: https://skmouse.tistory.com/entry/2021%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%B9%B4%EB%93%9C-%EC%A7%9D-%EB%A7%9E%EC%B6%94%EA%B8%B0-Java