[프로그래머스 Level.3] 카드 짝 맞추기 (2021 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT > 카드 짝 맞추기

 

 

 

문제 설명

 

 

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.

게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.

유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

 

 

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

 

• 카드는 커서를 이용해서 선택할 수 있습니다.
  • 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
• 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
  • [Enter] 키를 입력해서 카드를 뒤집었을 때
    • 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
    • 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.

 

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

 

다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.

아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.

 

예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.

 

[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회

 

[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회

 

[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회

 

위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.

 

---

 

[문제]

현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

 

 

 

[제한사항]

• board는 4 x 4 크기의 2차원 배열입니다.
• board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
  • 0은 카드가 제거된 빈 칸을 나타냅니다.
  • 1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
  • 뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
• r은 커서의 최초 세로(행) 위치를 의미합니다.
• c는 커서의 최초 가로(열) 위치를 의미합니다.
• r과 c는 0 이상 3 이하인 정수입니다.
• 게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.

 

---

 

[입출력 예]

board	r	c	result
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]	1	0	14
[[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]	0	1	16

 

---

 

입출력 예에 대한 설명

 

 

 

입출력 예 #1

문제의 예시와 같습니다.

 

 

 

 

입출력 예 #2

입력으로 주어진 게임 화면은 아래 그림과 같습니다.

 

 

위 게임 화면에서 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값은 16번 입니다.

 

 

 

 

 

 

 

나의 코드

import java.util.*;

// 참고 : https://loosie.tistory.com/m/170
class Solution {
    int[] dx = {-1, 1, 0, 0}; 
    int[] dy = {0, 0, -1, 1};
    public int solution(int[][] board, int r, int c) {
        int answer = Integer.MAX_VALUE;
        
        int cardNum = 0;
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if(board[i][j] != 0) cardNum++;
            }
        }
        
        cardNum /= 2;
        
        int[] card = new int[cardNum];
        for(int i=0; i<cardNum; i++) card[i] = i+1;
        
        ArrayList<String> comb = new ArrayList<>();
        dfs(card, comb, "", 0); // dfs로 제거할 카드의 순서 조합 전부 구하기
        // for(String s : comb) System.out.println(s);
        
        for(String s : comb) {
            String[] cardOrder = s.split("");
            
            int totalMove = 0;
            int x = r;
            int y = c;
            
            int[][] copyBoard = new int[4][4];
            for(int i=0; i<4; i++) {
                for(int j=0; j<4; j++) {
                    copyBoard[i][j] = board[i][j];
                }
            }
            
            for(String strTargetCard : cardOrder) {
                int targetCard = Integer.parseInt(strTargetCard);
                
                for(int i=0; i<2; i++) { // 첫번째(X번 1장) 카드 찾기 , 두번째(X번 2장) 카드 찾기
                    Node node = searchCard(x, y, targetCard, copyBoard); // bfs 개념으로 찾기
                    totalMove += node.cost;
                    x = node.x;
                    y = node.y;
                    copyBoard[x][y] = 0;
                    totalMove++; // 카드 선택(Enter)
                }
            }
            
            answer = Math.min(answer, totalMove);
        }
        
        return answer;
    }
    
    public void dfs(int[] card, ArrayList<String> comb, String cardComb, int depth) {
        if(depth == card.length) {
            comb.add(cardComb);
            return;
        }
        
        for(int i=0; i<card.length; i++) {
            if(!cardComb.contains("" + card[i])) {
                dfs(card, comb, cardComb + card[i], depth + 1);
            }
        }
    }
    
    public Node searchCard(int x, int y, int targetCard, int[][] copyBoard) {
        boolean[][] visited = new boolean[4][4];
        
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Node now = q.poll();
            
            if(copyBoard[now.x][now.y] == targetCard) return now;
            
            // 상하좌우 1칸
            for(int i=0; i<4; i++) {
                int nx = now.x + dy[i];
                int ny = now.y + dx[i];
                
                if(nx < 0 || ny < 0 || nx >= copyBoard.length || ny >= copyBoard.length || visited[nx][ny]) continue;
                
                q.offer(new Node(nx, ny, now.cost + 1));
                visited[nx][ny] = true;
            }
            
            // 컨트롤 + 상하좌우
            for(int i=0; i<4; i++) {
                int nx = now.x;
                int ny = now.y;
                
                while(true) {
                    nx += dy[i];
                    ny += dx[i];
                    
                    if(nx < 0 || ny < 0 || nx >= copyBoard.length || ny >= copyBoard.length) {
                        nx -= dy[i];
                        ny -= dx[i];
                        break;
                    }
                    
                    if(copyBoard[nx][ny] != 0) break;
                }
                
                if(visited[nx][ny]) continue;
                
                q.offer(new Node(nx, ny, now.cost + 1));
                visited[nx][ny] = true;
            }
        }
        
        return new Node(0, 0, 0);
    }
    
    class Node {
        int x;
        int y;
        int cost;
        
        Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}

 

풀이

1. 완전 탐색 dfs를 이용하여 제거할 카드 순서 조합을 전부 구한 후에 완전 탐색 bfs를 이용하여 해당 카드의 순서대로 카드를 찾아 제거한다. bfs를 할 때는 상하좌우로 한 칸씩 이동하는 것과 컨트롤을 누르고 상하좌우로 이동하는 것도 고려하도록 한다.
2. 우선 주어진 2차원 배열 board를 순회하면서 카드의 수를 구하고 같은 수의 카드가 2장씩 세트이므로 카드의 세트 수를 구하기 위해 2로 나눠준다.
3. 카드를 제거 할 순서 조합을 구하기 위하여 카드의 세트 수를 길이로 하여 card 배열을 만들고 카드의 번호는 1부터 시작하므로 인덱스 + 1로 하여 카드의 번호를 저장한다.
4. 카드를 제거 할 순서 조합을 구해 담을 ArrayList를 생성한다.
5. dfs를 이용하여 카드를 제거 할 순서 조합을 구한다.
6. 카드의 세트 수만큼 for문을 돌면서 cardComb 문자열이 카드의 번호를 포함하고 있지 않으면 해당 카드의 번호를 추가하여 depth를 1 증가시키고 dfs()를 재귀 호출한다.
7. 만약 depth가 카드의 세트 수와 같다면 조합을 만들어진 것이므로 ArrayList에 추가하면서 모든 조합을 구한다.
8. 이제 제거 할 카드의 순서 조합을 구하였으니 어떤 조합으로 카드를 제거했을 때 키 조작 횟수가 최소인지를 구하면 된다.
9. 제거 할 카드의 순서 조합을 담은 ArrayList를 순회하면서 board를 카피한 후에 bfs를 이용하여 제거 할 카드의 순서대로 제거하도록 한다.
10. 제거 할 카드의 조합에서 각 해당 카드는 세트를 제거해야 하므로 (c, r)에서 시작하여 bfs()를 이용하여 가장 가까운 첫 번째 제거 할 카드를 찾아 제거하고 제거한 카드의 위치에서 다시 해당 카드의 짝을 제거한다. 그리고 다음 카드를 제거할 때도 제거한 위치에서 시작하도록 한다.
11. 카드의 위치 x, y와 움직인 거리 cost를 담기 위한 Node 클래스를 생성하고 한 카드 번호당 세트를 찾아야 하므로 2번 반복하는 for문을 이용하여 bfs()를 이용하여 해당 카드를 찾고 카드를 찾은 비용을 totalMove에 더해주고 찾은 카드의 위치를 x, y에 저장하고 copyBoard[x][y]를 0(빈 칸)으로 바꿔준 후에 totalMove를 1 증가시켜준다. (Enter 키를 눌러 카드를 선택)
12. 이렇게 해당 조합으로 카드 짝을 모두 제거하여 구한 totalMove를 answer와 비교하여 최솟값을 answer에 저장하며 가장 최소의 횟수를 answer에 남게한 후에 반환하면 된다.
13. bfs()에서는 Node를 선언타입으로 하는 Queue를 생성하고 board와 크기가 같은 2차원 배열 visited를 생성한다.
14. 첫 위치 x, y와 cost를 0으로 하는 Node 객체를 생성하여 Queue에 담고 visited[x][y]를 true로 변경한다.
15. Queue가 빌 때까지 while문을 반복하면서 Queue의 첫 데이터인 Node를 가져오고 해당 위치의 카드 번호가 제거할 카드의 번호이면 해당 Node를 반환하고 아니라면 상하좌우로 한 칸씩 이동한 위치가 board의 좌표 범위를 벗어나지 않으면 해당 위치와 cost+1로 하는 Node 객체를 생성하여 Queue에 담고 해당 위치의 visited를 true로 변경한다.
16. 또한, 컨트롤을 누르고 상하좌우로 이동하는 경우도 고려해야 하기 때문에 상하좌우 각 while문을 이용하여 board의 값이 0이 아닐 때까지 이동하여 해당 위치의 visited가 true가 아니라면 해당 위치와 cost+1로 하는 Node 객체를 생성하여 Queue에 담고 해당 위치의 visited를 true로 변경한다.
17. 이렇게 시작 위치에서 가장 적은 cost로 제거할 카드로 이동했을 때의 Node를 반환하여 해당 Node의 값을 이용하여 횟수를 더해주고 다음 카드를 찾을 시작 위치에 이용하면 된다.