(2021카카오) 카드 짝 맞추기 Java

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

 

정답률 0.95%인 문제이다. 극악의 문제였으니, 너무 부담갖지는말되, 이런문제까지 풀 수있어야 카카오 개발자가 된다는 마음가짐으로 공부하자. 2021년 카카오 신입공채 1차 6번 문제였다.

 

조합에 관한 내용 , DFS, BFS에 관핸 내용은 확실하게 숙지해야겠다.

 

풀이

---

카카오 풀이 : tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

 

 

카드 종류가 최대 6개이므로, 어떤 카드부터 제거해 나갈지 정하는 방법은 6! 가지입니다. 예를 들어 카드가 3종류인 경우, 3종류 카드를 제거하는 순서는 다음과 같이 6가지입니다.  => Permutation 사용

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

위와 같이 카드를 제거하는 모든 순서에 대해서 각각 카드를 제거해 보고, 그중 키 조작 횟수가 가장 적은 방법을 찾으면 됩니다. 이때, 각 카드는 종류별로 2장씩이므로, 두 카드를 제거하는 순서에 따라 키 조작 횟수가 달라질 수 있음을 주의합니다. 즉, 현재 제거해야 되는 카드 번호 X에 대해서, 카드 하나를 XA, 다른 카드 하나를 XB라고 했을 때 다음 두 가지 경우에 대해 고려해 주면 됩니다. =>

• 현재 커서 위치 → XA 카드를 제거 → XB 카드를 제거
• 현재 커서 위치 → XB 카드를 제거 → XA 카드를 제거

만약 XB 카드를 나중에 제거했고, X 카드 다음으로 Y 카드를 제거해야 한다면 이번에는 다음과 같이 두 가지 경우를 고려합니다.

• 현재 커서 위치(XB 카드 위치) → YA 카드를 제거 → YB 카드를 제거
• 현재 커서 위치(XB 카드 위치) → YB 카드를 제거 → YA 카드를 제거

따라서 위와 같은 방법으로 카드를 제거하는 가능한 모든 방법을 고려해 주면 되며, “현재 커서 위치 → XA 카드를 제거”와 같이 커서를 이동시키는 최소 조작 횟수는 BFS 탐색을 이용하여 최단거리를 구하면 됩니다.

 

 

 

import java.util.*;

class Solution {
    ArrayList<int[]> orders;
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};

    public int solution(int[][] board, int r, int c) {
        int answer = Integer.MAX_VALUE;
        int n = 0;
        for (int[] row : board) {//개수세기
            for (int e : row) {
                if (e != 0) n++;
            }
        }
        n /= 2;//짝 개수
        int[] temp = new int[n];//12345...n
        for (int i = 0; i < n; i++) {
            temp[i] = i + 1;
        }
        orders = new ArrayList<>();//순열로 123 312 213 231..짝 뽑는순서
        permutation(n, n, new int[n], temp, 0, 0);

        for (int[] order : orders) {
            int total = 0;
            int[] point = new int[2];//최초커서위치 (r,c)
            point[0] = r;
            point[1] = c;
            int[][] cBoard = new int[4][4];//grid 만들기
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    cBoard[i][j] = board[i][j];
                }
            }
            for (int card : order) {//int[]인 order 즉, 순열로 나열한 순서 한가지씩. 123, 132, ...
                int cnt = 0;
                //목표 카드 찾기
                cnt += bfs(cBoard, card, point) + 1;
                //목표 카드 선택
                cBoard[point[0]][point[1]] = 0;
                System.out.println(point[0] + "," + point[1]);
                //짝 찾기
                cnt += bfs(cBoard, card, point) + 1;
                //짝 찾기 성공
                cBoard[point[0]][point[1]] = 0;
                System.out.println(point[0] + "," + point[1]);

                total += cnt;
            }
            System.out.println("total : " +total);
            System.out.println("---");
            answer = Math.min(total, answer);
        }

        return answer;
    }

        private int bfs(int[][] board, int target, int[] point) {
            int r = point[0];
            int c = point[1];
            Queue<int[]> que = new LinkedList<>();
            boolean[][] visited = new boolean[4][4];

            que.offer(new int[]{r, c, 0});
            visited[r][c] = true;

            while (!que.isEmpty()) {
                int[] p = que.poll();
                if (board[p[0]][p[1]] == target) {
                    point[0] = p[0];
                    point[1] = p[1];
                    return p[2];
                }
                //4방 탐색
                for (int d = 0; d < 4; d++) {
                    int nr = p[0] + dr[d];//direction 상하좌우 탐색
                    int nc = p[1] + dc[d];//direction 상하좌우 탐색
                    if (nr >= 0 && nr < 4 && nc >= 0 && nc < 4 && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    que.offer(new int[]{nr, nc, p[2] + 1});
                }
            }

            //ctrl + 4방 탐색
            for (int d = 0; d < 4; d++) {
                int[] result = findCard(board, p[0], p[1], d);
                if ((result[0] != p[0] || result[1] != p[1]) && !visited[result[0]][result[1]]) {
                    visited[result[0]][result[1]] = true;
                    que.offer(new int[]{result[0], result[1], p[2] + 1});
                }
            }
        }
        return 0;
    }

    private int[] findCard(int[][] board, int r, int c, int d) {
        r += dr[d];
        c += dc[d];
        while (r >= 0 && r < 4 && c >= 0 && c < 4) {
            if (board[r][c] != 0) {
                return new int[]{r, c};
            }
            r += dr[d];
            c += dc[d];
        }
        return new int[]{r - dr[d], c - dc[d]};
    }

    private void permutation(int n, int r, int[] perms, int[] input, int depth, int flag) {
        if (depth == r) {
            int[] temp = new int[n];
            System.arraycopy(perms, 0, temp, 0, n);
            orders.add(temp);
            return;
        }
        for (int i = 0; i < n; i++) {
            if ((flag & (1 << i)) == 0) {
                perms[depth] = input[i];
                permutation(n, r, perms, input, depth + 1, flag | (1 << i));
            }
        }
    }
}