developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테파이썬
  • 시계열분석
  • 삼성코테자바풀이
  • 카카오코테
  • c++디자인패턴
  • 통계분석
  • 삼성코테구현풀이
  • c++ 빌더 패턴
  • 삼성코테자바준비
  • 카카오코테java풀이
  • 데이터분석
  • 삼성코테기출
  • BOJ파이썬풀이
  • 삼성코테기출자바풀이
  • AR모형
  • 코테파이썬
  • 백준파이썬풀이
  • 운영체제인터럽트
  • Arima
  • SW역량테스트파이썬풀이
  • MA모형
  • ARIMA모형
  • SW역량테스트파이썬
  • 삼성코테준비
  • 삼성코테자바꿀팁
  • 시계열
  • 삼성코테파이썬풀이
  • 통계학
  • 삼성코테파이썬준비
  • 삼성코테구현문제추천

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기(JAVA)
알고리즘/알고리즘문풀

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

2022. 5. 7. 01:26

❓ 문제 - 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번이상 살피자...!!!!!!!!!!!!!!!

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 대기업 승범이네 17831번 (JAVA, Python)  (0) 2022.05.16
BOJ - 우수 마을 1949번 (JAVA, Python)  (0) 2022.05.11
BOJ - 온풍기 안녕! 23289번 (JAVA)  (0) 2022.04.30
BOJ - 마법사 상어와 블리자드 21611번 (JAVA)  (0) 2022.04.30
BOJ - 마법사 상어와 비바라기 21610번 (JAVA)  (0) 2022.04.30
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 대기업 승범이네 17831번 (JAVA, Python)
    • BOJ - 우수 마을 1949번 (JAVA, Python)
    • BOJ - 온풍기 안녕! 23289번 (JAVA)
    • BOJ - 마법사 상어와 블리자드 21611번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바