2021 KAKAO BLIND RECRUITMENT : 카드 짝 맞추기(리뷰 필요)

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

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

 

// 코드

import java.util.*;
 
class Solution {
    
    static final int INF = Integer.MAX_VALUE;
    static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] Board;
    
    class Point {
        // 행, 열, 조작 횟수
        int row, col, cnt;
        
        Point(int row, int col, int cnt) {
            this.row = row;
            this.col = col;
            this.cnt = cnt;
        }
        
    }
    
    int bfs(Point src, Point dst) {
        
        boolean[][] visited = new boolean[4][4];
        Deque<Point> deq = new ArrayDeque<>();
        
        deq.add(src);
        while(!deq.isEmpty()) {
            Point curr = deq.pop();            
            if(curr.row == dst.row && curr.col == dst.col) 
                return curr.cnt;
            
            for(int i=0; i<4; ++i) {
                int nr = curr.row + dir[i][0], nc = curr.col + dir[i][1];                
                if(nr < 0 || nr > 3 || nc < 0 || nc > 3) continue;
                
                if(!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    deq.add(new Point(nr, nc, curr.cnt + 1));
                }
                
                for(int j=0; j<2; ++j) {
                    if(Board[nr][nc] != 0) break;
                    if(nr + dir[i][0] < 0 || nr + dir[i][0] > 3 
                      || nc + dir[i][1] < 0 || nc + dir[i][1] > 3) break;
                    
                    nr += dir[i][0];
                    nc += dir[i][1];                    
                }
                
                if(!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    deq.add(new Point(nr, nc, curr.cnt + 1));
                }
                
            }
            
        }
        
        return INF;
    }
    
    int permutate(Point src) {
        int ret = INF;
        
        // 1~6번 까지 카드
        for(int num=1; num<=6; ++num) {
            List<Point> card = new ArrayList<>();
            // 해당 카드의 위치를 찾는다.
            for(int i=0; i<4; ++i) {
                for(int j=0; j<4; ++j) {
                    if(Board[i][j] == num) {
                        card.add(new Point(i, j, 0));
                    }
                }
            }
            
            if(card.isEmpty()) continue;
            
            //두 개의 카드를 뒤집는다.
            int one = bfs(src, card.get(0)) 
                + bfs(card.get(0), card.get(1)) + 2;
            
            int two = bfs(src, card.get(1)) 
                + bfs(card.get(1), card.get(0)) + 2;
            
            // 카드를 뒤집었으니 해당카드를 지워준다.
            for(int i=0; i<2; i++) 
                Board[card.get(i).row][card.get(i).col] = 0;            
            
            ret = Math.min(ret, one + permutate(card.get(1)));
            ret = Math.min(ret, two + permutate(card.get(0)));
            
            // 뒤집었던 카드를 복원해준다.
            for(int i=0; i<2; i++) 
                Board[card.get(i).row][card.get(i).col] = num;
            
        }
        
        if(ret == INF) return 0;
    
        return ret;
    }
    
    public int solution(int[][] board, int r, int c) {        
        Board = board;        
        return permutate(new Point(r, c, 0));
    }
}