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

🖇️ 문제 링크

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

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다. 게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.

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

 

---

⌨️ 코드

import java.util.*;

class Solution {
    final int INF = (int)1e9;
    int[][] Board;
    
    public int solution(int[][] board, int r, int c) {
        Board = board;
        return perm(new Point(r, c, 0));
    }
    
    // 카드 지우는 순서 결정
    public int perm(Point cur) {
        int ret = INF;
        for(int num = 1; num <= 6; num++) {
            List<Point> list = new ArrayList<>();
            // 숫자 카드 두 개 넣음
           	for(int r = 0; r < 4; r++)
                for(int c = 0; c < 4; c++)
                    if(Board[r][c] == num)
                        list.add(new Point(r, c, 0));
            
            // 못찾았으면 다음 번호로
            if(list.isEmpty())
                continue;
           	
            // 카드 두 장 중 어떤 카드 부터 할지 결정
            int first = bfs(cur, list.get(0)) + bfs(list.get(0), list.get(1)) + 2;
            int second = bfs(cur, list.get(1)) + bfs(list.get(1), list.get(0)) + 2;
            
            // 카드 뒤집기
            Board[list.get(0).y][list.get(0).x] = 0;
            Board[list.get(1).y][list.get(1).x] = 0;
            
            // 둘 중 작은 것
            ret = Math.min(ret, first + perm(list.get(1)));
            ret = Math.min(ret, second + perm(list.get(0)));
            
            // 카드 복원
            Board[list.get(0).y][list.get(0).x] = num;
            Board[list.get(1).y][list.get(1).x] = num;
        }
        
        // 찾을 카드가 없으면 0
        if(ret == INF)
            return 0;
        
        return ret;
    }
    
    public int bfs(Point start, Point end) {
        boolean[][] visited = new boolean[4][4];
        int[] dy = {-1, 0, 1, 0};
        int[] dx = {0, 1, 0, -1};
        Queue<Point> q = new LinkedList<>();
        q.add(start);
        visited[start.y][start.x] = true;
        
        while(!q.isEmpty()) {
        	Point cur = q.poll();
            if(cur.y == end.y && cur.x == end.x)
                return cur.cnt;
            
           	for(int d = 0; d < 4; d++) {
                int ny = cur.y + dy[d];
                int nx = cur.x + dx[d];
                
                if(ny < 0 || nx < 0 || ny >= 4 || nx >= 4)
                    continue;
               	
                if(!visited[ny][nx]) {
                    visited[ny][nx] = true;
                    q.add(new Point(ny, nx, cur.cnt + 1));
                }
                
                // ctrl + 방향키 연산
                for(int i = 0; i < 2; i++) {
                   	if(Board[ny][nx] != 0) break;
                    int nny = ny + dy[d], nnx = nx + dx[d];
                    if(nny < 0 || nnx < 0 || nny >= 4 || nnx >= 4) break;
                    ny = nny;
                    nx = nnx;
                }
                
                if(!visited[ny][nx]) {
                    visited[ny][nx] = true;
                    q.add(new Point(ny, nx, cur.cnt + 1));
                }
            } 
        }
        return INF;
    }
}

class Point {
    int y, x, cnt;
    
    Point(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0