2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기(JAVA)

❓ 문제 - 2021 KAKAO BLIND RECRUITMENT 카드 짝 맞추기 - JAVA 풀이법

출처 

(https://programmers.co.kr/learn/courses/30/lessons/72415?language=java)

 

 

 

 

📝 문제해결법 

1. DFS로 순열로 카드 번호 뽑는 순서를 정한 후 BFS로 이 순서에 맞춰 최단 거리로 이동 처리하면서 이동 거리의 최솟값을 갱신한다.

 

2. DFS로 순열 구하기

• nodes라는 Node의 2차원 배열로 각 인덱스는 카드의 숫자이고 nodes[i][0], nodes[i][1] 은 i번째 숫자의 Node를 나타내며 Node를 통해 카드의 위치 x, y를 구할 수 있다.
• permu라는 Node 배열로 각 카드의 번호를 뽑는 순서에 맞게 노드의 위치들을 정한다.
• 카드의 번호 대로 뽑을 때 (1->2->3) 번의 순서로 뽑을 때 1에서도 2개의 카드중 누굴 먼저 뒤집으로 갈 것인지에 대한 순서도 포함되어야 한다.
• 따라서 nodes[i]에 첫 번째에 카드를 먼저 뒤집고 -> 두 번째 카드 뒤집은 경우 / nodes[i]에 두 번째 카드를 먼저 뒤집고 첫 번째 카드를 먼저 뒤집은 경우인 모든 경우를 나누어서 순열을 만들어야 한다.

3. BFS로 순열 구하기

• 해당 카드 뒤집는 순열의 순서에 맞춰서 BFS로 이동하면서 최단 거리를 찾는다.
• 이동하는 방법은 총 두 가지 인데, 4방 탐색으로 범위를 넘지 않도록 하면서 카드를 찾는 방식과, 컨트롤 + 4방 탐색으로 이동하는 방식 두 가지가 있다. 
• 4방 탐색으로 이동하는 경우 방문하지 않은 곳만 체크해줘서 이동하면서 이동 거리를 구하면 된다.
• 하지만 컨트롤 + 4방 탐색으로 이동하는 경우 문제에서 이동 범위 내에 이동할 수 있는 카드가 존재한다는 조건이 있으므로 이것을 유념해서 구현해줘야 한다. 그리고 컨트롤 + 4방 탐색으로 가다가 만약 범위를 넘어나는 곳까지 다 봤는데도 카드가 존재하지 않는다면 경계에 있는 곳으로 이동 처리해준다.
• 한번의 카드의 번호를 뒤집는 순서 내에서 BFS로 해당 카드까지의 최단 거리를 구하면 카드의 위치 s_x, s_y를 꼭 그 전에 도착한 위치로 변경해줘야 한다.

 

💻 소스코드 

import java.util.LinkedList;
import java.util.Queue;

public class Kakao_BLIND_2021_6 {
    public static void main(String[] args) {
        int ans = solution(new int[][]{{1,0,0,3},{2,0,0,0},{0,0,0,2},{3,0,1,0}}, 1, 0);
        System.out.println(ans);
    }

    public static boolean[] use;
    public static Node[] permu;

    public static int min_ans = Integer.MAX_VALUE;

    public static Node[][] nodes;
    public static class Node {
        int x;
        int y;
        int num;
        public Node(int x, int y, int num){
            this.x = x;
            this.y = y;
            this.num = num;

        }
    }

    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static int[][] bd;
    public static int solution(int[][] board, int r, int c) {
        int answer = 0;
        use = new boolean[7];
        nodes = new Node[7][2];
        bd = board;
        int num = 0;
        for(int i=0;i<4;i++) {
            for(int j=0;j<4;j++) {
                if(board[i][j] != 0) {
                    num++;
                    if(nodes[board[i][j]][0] == null){
                        nodes[board[i][j]][0] = new Node(i, j, board[i][j]);
                    } else {
                        nodes[board[i][j]][1] = new Node(i, j, board[i][j]);
                    }

                }
            }
        }
        permu = new Node[num];
        dfs(0, num/2, r, c);
        answer = min_ans;
        return answer;
    }

    public static void dfs(int depth, int end, int r, int c){
        if(depth == end){
            int dis = bfs(r, c);
            min_ans = Math.min(min_ans, dis);
            return;
        }

        for(int i=1;i<=end;i++){
            if(use[i]) continue;

            // 첫 번째가 먼저
            permu[2*depth] = new Node(nodes[i][0].x, nodes[i][0].y, nodes[i][0].num);
            permu[2*depth+1] = new Node(nodes[i][1].x, nodes[i][1].y, nodes[i][1].num);
            use[i] = true;
            dfs(depth+1, end, r, c);
            // 두 번째가 먼저
            permu[2*depth+1] = new Node(nodes[i][0].x, nodes[i][0].y, nodes[i][0].num);
            permu[2*depth] = new Node(nodes[i][1].x, nodes[i][1].y, nodes[i][1].num);

            dfs(depth+1, end, r, c);
            use[i] = false;
        }
    }

    public static int bfs(int r, int c){
        int dis = 0;
        int[][] copy = new int[4][4];
        for(int i=0;i<4;i++)
            copy[i] = bd[i].clone();

        int s_x = r;
        int s_y = c;

        for(Node node_p:permu){
            boolean[][] visited = new boolean[4][4];

            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{s_x, s_y, 0});
            visited[s_x][s_y] = true;
            while (!q.isEmpty()){
                int[] node = q.poll();
                if(node[0] == node_p.x && node[1] == node_p.y){
                    dis += (node[2]+1);
                    copy[node[0]][node[1]] = 0;
                    break;
                }

                // 상, 하, 좌, 우 한칸씩만
                for(int d=0;d<4;d++){
                    int nx = node[0] + dx[d];
                    int ny = node[1] + dy[d];
                    if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

                    if(!visited[nx][ny]){
                        visited[nx][ny] = true;
                        q.add(new int[]{nx, ny, node[2]+1});
                    }
                }

                // 컨트롤 + 상, 하, 좌, 우

                for(int d=0;d<4;d++){
                    int nx = node[0];
                    int ny = node[1];

                    while (true){
                        nx += dx[d];
                        ny += dy[d];
                        if(nx < 0 || nx >= 4 || ny < 0 || ny >= 4){
                            nx -= dx[d];
                            ny -= dy[d];
                            if(!visited[nx][ny]) {
                                visited[nx][ny] = true;
                                q.add(new int[]{nx, ny, node[2] + 1});
                            }
                            break;
                        }
                        if(copy[nx][ny] > 0){
                            visited[nx][ny] = true;
                            q.add(new int[]{nx, ny, node[2]+1});
                            break;
                        }
                    }
                }


            }
            s_x = node_p.x;
            s_y = node_p.y;
        }




        return dis;
    }

}

 

 

🤷 느낀점 및 문제 푸는 과정

• 처음에 문제를 정확히 안 읽어서 bfs로 최단 거리 구하는 것 말고 그냥 맨허튼 거리방식으로 거리 구하도록 했는데 ... 자꾸 틀려서 뭔가 했다.
• 알고리즘 문제를 처음 접할 때 문제를 3번이상 살피자...!!!!!!!!!!!!!!!