[Lv.3] 카드 짝 맞추기 -자바

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int moveCount;
    int[][] gameBoard;
    public int solution(int[][] board, int r, int c) {
        int answer = 0;
        moveCount=Integer.MAX_VALUE;
        gameBoard=board.clone();
        if(board[r][c]!=0)
            dfs(1,r,c,board[r][c]);
        else dfs(0,r,c,board[r][c]);
        return moveCount;
    }

    void dfs(int depth, int x,int y,int select){
        if(depth>=moveCount)
            return;
        if(select!=0){
            for (int i = 0; i < gameBoard.length; i++) {
                for (int j = 0; j < gameBoard[i].length; j++) {
                    if(gameBoard[i][j]==select&&!(x==i&&y==j)){
                        int minPath=calculateMinPath(x,y,i,j);
                        minPath++;
                        gameBoard[x][y]=gameBoard[i][j]=0;
                        dfs(depth+minPath,i,j,0);
                        gameBoard[x][y]=gameBoard[i][j]=select;
                        return;
                    }
                }
            }
        }else{
            boolean endFlag=true;
            for (int i = 0; i < gameBoard.length; i++) {
                for (int j = 0; j < gameBoard[i].length; j++) {
                    if(gameBoard[i][j]!=0){
                        endFlag=false;
                        int minPath=calculateMinPath(x,y,i,j);
                        minPath++;
                        dfs(depth+minPath,i,j,gameBoard[i][j]);
                    }
                }
            }
            if(endFlag){
                moveCount=Math.min(moveCount,depth);
            }
        }
    }


    public int calculateMinPath(int x, int y, int i, int j) {
        Queue<Point> queue= new LinkedList<>();
        queue.add(new Point(x,y,0));
        int move=0;
        boolean[][] visited=new boolean[4][4];
        while (!queue.isEmpty()){
            Point point = queue.poll();
            if(point.x==i&&point.y==j){
                return point.move;
            }

            visited[point.x][point.y]=true;
            int[] addX=new int[]{1,-1,0,0};
            int[] addY=new int[]{0,0,1,-1};
            for (int k = 0; k < 4; k++) {
                int nX= point.x+addX[k];
                int nY= point.y+addY[k];
                if(nX>=0&&nX<4&&nY>=0&&nY<4&&!visited[nX][nY]){
                    queue.add(new Point(nX,nY, point.move+1));
                }
            }
            //ctrl
            if(point.y>0){
                int k;
                for (k = point.y-1; k >=0; k--) {
                    if(gameBoard[point.x][k]!=0)
                        break;
                }
                Point pt = new Point(point.x,k<0?0:k, point.move+1);
                if(!queue.contains(pt)&&!visited[pt.x][pt.y])
                    queue.add(pt);
            }
            if(point.y<3){
                int k;
                for (k = point.y+1;  k< 4; k++) {
                    if(gameBoard[point.x][k]!=0)
                        break;
                }
                Point pt = new Point(point.x,k>3?3:k, point.move+1);
                if(!queue.contains(pt)&&!visited[pt.x][pt.y])
                    queue.add(pt);
            }
            if(point.x>0){
                int k;
                for (k = point.x-1; k >=0; k--) {
                    if(gameBoard[k][point.y]!=0)
                        break;
                }
                Point pt = new Point(k < 0 ? 0 : k, point.y, point.move + 1);
                if(!queue.contains(pt)&&!visited[pt.x][pt.y])
                    queue.add(pt);
            }
            if(point.x<3){
                int k;
                for (k = point.x+1;  k< 4; k++) {
                    if(gameBoard[k][point.y]!=0)
                        break;
                }

                Point pt = new Point(k>3?3:k,point.y, point.move+1);
                if(!queue.contains(pt)&&!visited[pt.x][pt.y])
                    queue.add(pt);
            }
        }
        return -1;
    }
    class Point{
        int x,y,move;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Point point = (Point) o;

            if (x != point.x) return false;
            return y == point.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    ", move=" + move +
                    '}';
        }

        public Point(int x, int y, int move) {
            this.x = x;
            this.y = y;
            this.move=move;
        }
    }
}

---

구현문제였다..

구현 자체의 난이도는 중간 정도였다고 생각하는데, bfs+dfs가 섞이기도 했고 범위 산정에 까다로운 부분이 있어 꽤 어려웠던 문제였다..

 

 

카드 짝을 맞추고 다음 카드로 이동할 때 항상 최단 경로에 있는 카드만 찾아가지 않는 경우에도 전체적으로 최소가 될 수 있다고 생각했다. 따라서, 카드 짝을 맞춘 후 남아있는 모든 카드를 대상으로 dfs를 다시 수행하는 방식으로 큰 틀을 잡았다.

 

우선, 주어진 지점이 카드가 있는 위치라면 바로 enter를 누르는게 그 어떤 경우보다 빠르기에 dfs를 처음 진입하는 지점에서 분기를 해주었다.

dfs의 경우

이미 한장을 enter한 경우 그 값을 select에 넣어 들어오게 되고 이 값을 바탕으로 짝꿍 카드를 찾아 해당 카드까지의 최단 경로를 계산하고 해당 경로로 이동하고 enter를 누른다 (즉 , minPath+1 만큼 이동 수를 증가시킨다)

짝을 맞추게 된 카드는 0과 같게 되므로, 0으로 값을 변경해준 후 짝꿍 카드 위치에서 다시 dfs를 시작한다. (여기서 enter를 누른 카드는 없기에 select 값은 0으로 한다.)

enter를 하지 않은 경우 현재 보드에 남아있는 모든 카드를 대상으로 해당 카드 까지의 최단 경로를 계산 하고 반복해서 dfs를 진행한다. (즉, minPath+1(enter)를 한 후 dfs를 진행하여 해당 카드의 짝을 찾는다)

 

이렇게 쭉 반복을 하고, 만약 enter를 하지 않은 경우에 카드를 하나도 찾지 못하게 된다면 모든 카드의 짝을 뒤집었다는 의미이므로 현재 이동 횟수와 최소 이동횟수를 비교하여 최솟값을 갱신한다.

 

bfs의 경우 ( x,y에서 i,j로의 최단 경로를 찾는 로직 )

현재 지점을 기준으로 상하좌우 그리고 ctrl+ 상하좌우로 이동가능 한 경로를 대상으로 bfs를 수행한다.

여기서, Point객체의 equals를 정의해서 Point끼리 비교를 진행할 수 있게 해주고, 큐에 이미 해당 좌표가 들어있는 경우 추가하지 않게 한다. (큐에 해당 좌표가 들어있다는 뜻은 이미 앞전에 해당 좌표로 이동가능하게 되었다는 뜻이 되고, 그렇다면 Point에서의 move는 현재의 move보다 항상 작거나 같기 때문이다)

이렇게 bfs를 진행하게 되면, 해당 지점으로의 최단 경로를 빠르게 계산할 수 있게 된다.

 

정리하자면

1. 시작점에 카드가 있다면 바로 선택하고 아니라면 선택하지 않은 상태로 dfs를 진행한다.

2-1. dfs에선 선택한 카드가 있다면 해당 카드의 짝을 찾아(bfs) 선택 후 두 카드 모두 뒤집는다.

2-2. 선택한 카드가 없다면 가능한 카드를 모두 찾아 최단경로(bfs)를 더해주고 선택한 후 해당 카드 위치에서 dfs를 다시 진행한다.

2-3. 선택할 카드가 없다면 (즉, 모든 카드가 뒤집어졌다면) 이동 횟수를 최솟값과 비교하여 갱신한다.

3. 문제에서 주어진 상하좌우, ctrl+상하좌우 로직에 맞춰 이동하는 좌표들을 bfs를 이용하여 탐색하고 목적지에 도착하는 경우 최단 경로를 return한다.