[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추 기 - 자바(JAVA)

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

코딩테스트 연습 - 카드 짝 맞추기

 

문제 해석

4 x 4 크기의 격자 형태의 화면에 카드 16장이 뒷면으로 존재합니다.

16장의 카드는 8가지 캐릭터 그림이 무작위로 2장씩 존재합니다.

 

게임에서 카드를 선택하는 방법은 다음과 같습니다

 

방향키(상하좌우)로 이동하며 1칸씩 이동합니다.

 

이때 Ctrl 키를 누른 상태에서 방향키를 누르면 가장 가까운 카드로 한 번에 이동합니다.

• 이때 만약 해당 방향에 카드가 존재하지 않으면 가장 마지막 칸을 이동합니다
• 또 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다

Enter키를 입력해서 카드를 뒤집을 수 있습니다.

 

이러한 게임 방식 속에서 카드를 제거하는데 필요한 키 조작 횟수의 최솟값을 구해보려고 합니다.

 

키 조작 횟수가 증가되는 방식

1. Ctrl + 방향키

2. 방향키

3. Enter

 

 

문제 풀이 전 설계

최초 커서의 위치와 , 게임보드의 상태가 주어집니다.

문제에서 카드의 종류는 1, 2, 3, 4 ,5 ,6으로 6개 주어집니다.

 

이때 키 조작 횟수의 최솟값을 구하기 위해서는 어떤 캐릭터를 먼저 없애느냐가 중요할 것 같습니다.

경우의 수 = 6!

 

또한 이동할 때 Ctrl으로 이동하는것이 좋을지 방향키로 이동해야 할지를 적절하게 선택하면서 이동해야 할 것 같습니다.

bfs를 활용하여 1칸이동하는 사방 탐색을 구현하고, 또한 Ctrl으로 이동하는 사방 탐색을 구현합니다.

그러면서 중복방문하는 경우에는 최소의 의미가 없어지기 때문에 visited배열로 이미 탐색된 것은 탐색하지 않습니다.

 

그리고 원하는 카드의 종류를 찾는 즉시 종료합니다.

 

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    
    static boolean[] visited;
    static int[] orders;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int[][] originBoard;
    static int curY;
    static int curX;
    static int result;

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

        public Point(int y, int x, int move) {
            this.y = y;
            this.x = x;
            this.move = move;
        }
    }
    
    public int solution(int[][] board, int r, int c) {
        originBoard = copyBoard(board);
        curY = r;
        curX = c;
        result = Integer.MAX_VALUE;
        Set<Integer> cards = Arrays.stream(board)
                                   .flatMapToInt(Arrays::stream)
                                   .boxed()
                                   .collect(Collectors.toSet());

        int kindCount = cards.size() - 1;
        visited = new boolean[kindCount];
        orders = new int[kindCount];
        permutation(kindCount, 0);
        return result;
    }
    private static void permutation(int kindCount, int cnt) {

        if (cnt == kindCount) {
            gameStart(orders);
            return;
        }

        for (int i = 0; i < kindCount; i++) {
            if (visited[i]) {
                continue;
            }
            orders[cnt] = i + 1;
            visited[i] = true;
            permutation(kindCount, cnt + 1);
            visited[i] = false;
        }
    }

    private static void gameStart(int[] orders) {
        Queue<Integer> order = new LinkedList<>();
        Arrays.stream(orders)
              .forEach(order::add);
        int[][] startBoard = copyBoard(originBoard);
        Point cursor = new Point(curY, curX, 0);
        int move = 0;
        while (!order.isEmpty()) {
            int target = order.poll();
            //첫번째 카드 찾기
            move += bfs(startBoard, target, cursor);
            //찾은 카드 0으로 제거
            startBoard[cursor.y][cursor.x] = 0;
            //enter
            move += 1;

            //두번째 카드 찾기
            move += bfs(startBoard, target, cursor);
            //찾은 카드 0으로 제거
            startBoard[cursor.y][cursor.x] = 0;
            //enter
            move += 1;

        }
        result = Math.min(result, move);

    }

    private static int bfs(int[][] startBoard, int target, Point cursor) {
        Queue<Point> bfsQ = new LinkedList<>();
        boolean[][] visited = new boolean[4][4];
        Point tempCursor = new Point(cursor.y, cursor.x, 0);
        visited[tempCursor.y][tempCursor.x] = true;
        bfsQ.add(new Point(tempCursor.y, tempCursor.x, 0));

        while (!bfsQ.isEmpty()) {
            Point cur = bfsQ.poll();
            int curY = cur.y;
            int curX = cur.x;
            int curMove = cur.move;

            if (startBoard[curY][curX] == target) {
                cursor.y = curY;
                cursor.x = curX;
                return curMove;
            }

            //상하좌우 1칸 move
            for (int k = 0; k < 4; k++) {
                int ny = curY + dy[k];
                int nx = curX + dx[k];

                if (ny < 0 || nx < 0 || nx > 3 || ny > 3) {
                    continue;
                }
                if (visited[ny][nx]) {
                    continue;
                }

                visited[ny][nx] = true;
                bfsQ.add(new Point(ny, nx, curMove + 1));
            }

            //Ctrl + 상하좌우 move
            for (int i = 0; i < 4; i++) {
                Point afterMove = ctrlMove(curY, curX, i, startBoard);
                int ny = afterMove.y;
                int nx = afterMove.x;

                if (visited[ny][nx]) continue;

                visited[ny][nx] = true;
                bfsQ.add(new Point(ny, nx, curMove + 1));
            }

        }

        return 0;
    }

    static Point ctrlMove(int curY, int curX, int k, int[][] startBoard) {
        curY += dy[k];
        curX += dx[k];
        while (curY >= 0 && curX >= 0 && curY < 4 && curX < 4) {
            if (startBoard[curY][curX] != 0) {
                return new Point(curY, curX, 0);
            }
            curY += dy[k];
            curX += dx[k];
        }
        return new Point(curY - dy[k], curX - dx[k], 0);
    }


    private static int[][] copyBoard(int[][] board) {
        return Arrays.stream(board)
                     .map(int[]::clone)
                     .toArray(int[][]::new);
    }
}