프로그래머스 카드 짝 맞추기 (JAVA)

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

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

 

저는 해당 문제를 BFS를 이용하여 문제를 해결하였습니다.

BFS를 한칸 이동과 ctrl을 눌렀을 때 끝까지 가거나 카드까지 가는 것을 둘 다 넣었고, 카드를 오픈하는 것도 넣고 BFS를 진행하였습니다. 카드 오픈은 빈칸이거나, 짝을 맞추려고 오픈 시킨 카드가 있다면 BFS에 넣지 않았습니다.

방문 체크는 Set<String>을 이용하여 했습니다.

Node의 toString 재정의하여 Node의 toString이 Set에 있는지를 판단하여 있다면 방문 한 것이기 떄문에 BFS에 넣지 않고 처음 방문하는 것이라면 BFS에 넣었습니다.

import java.util.*;
class Solution {
    static class Node{
        int y;
        int x;
        int[][] map;
        int card;
        
        public Node(int y, int x , int[][] map , int card){
            this.y = y;
            this.x = x;
            this.map = map;
            this.card = card;
        }
        
        public boolean openCard(){
            if(map[y][x] == 0){
                return false;
            }
            if(card == 0){
                card = map[y][x];
                map[y][x] = 0;
                return true;
            }else if(card == map[y][x]){
                map[y][x] = 0;
                card = 0;
                // System.out.println("remove");
                // System.out.println(this);
                return true;
            }
            return false;
        }
        
        public Node copy(){
            Node temp = new Node(y,x,map,card);
            temp.map = copyArr(this.map,SIZE);
            return temp;
        }
        
        public boolean checkClear(){
            for(int i = 0 ; i < SIZE ; i++){
                for(int j = 0 ; j < SIZE ; j++){
                    if(map[i][j] != 0){
                        return false;
                    }
                }
            }
            return true;
        }
        public String toString(){
            return y + "," + x + "," + Arrays.deepToString(map) + "," + card;
        }
    }
    public int solution(int[][] board, int r, int c) {
        int answer = 0;
        answer = bfs(board,r,c);
        return answer;
    }
    
    private static final int[] dy = {-1,0,1,0};
    private static final int[] dx = {0,1,0,-1};
    
    private static final int SIZE = 4;
    
    private static int bfs(int[][] board, int r, int c){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(r,c,board,0));
        Set<String> visited = new HashSet<>();
        int time = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size; s++){
                Node now = q.poll();
                // System.out.println(now);
                int y = now.y;
                int x = now.x;
                int[][] map = now.map;
                int card = now.card;
                Node node = now.copy();
                if(node.openCard() && !visited.contains(node.toString())){
                    if(node.checkClear()){
                        return time + 1;
                    }
                    visited.add(node.toString());
                    q.offer(node);
                }
                for(int i = 0 ; i < 4; i++){
                    int ny = y + dy[i];
                    int nx = x + dx[i];
                    if(checkBound(ny,nx,SIZE)){
                        Node temp = new Node(ny,nx,map,card);
                        if(!visited.contains(temp.toString())){
                            visited.add(temp.toString());
                            q.offer(temp);
                        }
                    }
                    while(checkBound(ny,nx,SIZE) && map[ny][nx] == 0){
                        ny += dy[i];
                        nx += dx[i];
                    }
                    if(!checkBound(ny,nx,SIZE)){
                        ny -= dy[i];
                        nx -= dx[i];
                    }
                    
                    Node temp = new Node(ny,nx,map,card);
                    if(!visited.contains(temp.toString())){
                        visited.add(temp.toString());
                        q.offer(temp);
                    }
                }
            }
            time++;
            // if(time == 3){
            //     break;
            // }
        }
        return -1;
    }
    private static boolean checkBound(int ny,int nx,int size){
        if(ny >= 0 && ny < size && nx >= 0 && nx < size){
            return true;
        }
        return false;
    }
    
    public static int[][] copyArr(int[][] arr,int n){
        int[][] temp = new int[n][n];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                temp[i][j] = arr[i][j];
            }
        }
        return temp;
    }
}