[프로그래머스] 카드 짝 맞추기

문제

---

현재 카드가 놓인 상태를 나타내는 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) 입니다.

 

자세한 문제 설명은 본문참조

https://programmers.co.kr/learn/courses/30/lessons/72415?language=java# 

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

 

 

풀이

---

처음에는 DFS 방식으로 모든 경우의 수 속에 가장 짧은 경로를 찾았다. 예시 답은 찾았으나 시간초과가 났다.

 

그래서 찾아본 결과 알고리즘의 순서는 아래와 같다.

1. 카드의 종류를 찾는다.
2. 카드의 종류를 뒤집을 순서를 순열로 정한다.
3. 뒤집는 경로중 가장짧은 경로를 찾는다.

이렇게 하면된다.

그 동안 풀던 최단경로찾기 문제와 좀 다른 느낌이다. 최단경로 문제는 풀어도 풀어도 끝이 없는 느낌이다.

 

순열 코드다.

static void Permutation(List<Integer> card, List<Integer> result, int r, int size){

    if( r == size){
        List<Integer> temp = new ArrayList<Integer>();
        for(int num : result){
            temp.add(num);
        }
        list.add(temp);            
        return;
    }

    for(int i = 0 ; i < card.size() ; i++){
        result.add(card.remove(i));
        Permutation(card, result, r + 1, size);
        card.add(i, result.remove(result.size() - 1));
    }
}

위 코드를 통해 1, 2, 3의 세가지 종류의 카드가 있다면,

1 -> 2 -> 3

1 -> 3 -> 2

2 -> 1 -> 3

2 -> 3 -> 1

3 -> 1 -> 2

3 -> 2 -> 1  이렇게 경우의 수를 만든다.

 

이렇게 만들어진 경우의 수를 가지고 찾는 경로를 찾아서 더하는 코드는 아래와 같다.

for(List<Integer> order : list){
    int sum = 0;
    int[][] copyboard = copyBoard(board);
    vertex v = new vertex(r, c, 0);

    for(int cardNumber : order){
        int cnt = 0;
        v = bfs(copyboard, cardNumber, v.r, v.c);
        copyboard[v.r][v.c] = 0;
        cnt += v.count + 1;

        v = bfs(copyboard, cardNumber, v.r, v.c);
        copyboard[v.r][v.c] = 0;
        cnt += v.count + 1;

        sum += cnt;
    }

    answer = Math.min(answer, sum);
}

경로를 찾는 코드는 bfs 방식을 사용했다. 최단경로 찾기의 경우에는 DFS 는 시간이 많이 걸리는 편이다. 그동안 이럴때 다익스트라 알고리즘도 많이 사용했는데 시도해보면 좋겠다.

 

너비우선탐색 코드다.

static vertex bfs(int[][] board, int cardNumber, int r, int c){

    Queue<vertex> queue = new LinkedList<vertex>();
    queue.add(new vertex(r, c, 0));
    boolean[][] visited = new boolean[4][4];

    while(!queue.isEmpty()){

        vertex v = queue.poll();
        if(board[v.r][v.c] == cardNumber){
            return v;
        }

        for(int i = 0 ; i < 4 ; i++){

            int nr = v.r + dy[i];
            int nc = v.c + dx[i];

            if(nc < 0 || nc >= 4 || nr < 0 || nr >= 4 || visited[nr][nc]){ continue; }

            visited[nr][nc] = true;
            queue.add(new vertex(nr, nc, v.count + 1));
        }

        for(int i = 0 ; i < 4 ; i++){
            vertex nv = findCtrlMove(board, v.r, v.c, i);

            if((nv.r == v.r && nv.c == v.c) || visited[nv.r][nv.c]) {continue;}

            visited[nv.r][nv.c] = true;
            nv.count = v.count + 1;
            queue.add(nv);
        }          
    }

    return null;
}

이문제의 경우에는 4방향을 한칸씩 가는 경우와 Ctrl + 방향키로 한번에 벽까지나 카드까지 가는 경우의 수를 나누어서 판단해주어야 한다.

 

 

 

이렇게 구해진 횟수에 + 1 씩을 더 더해주어 카드를 뒤집을때의 조작수도 더해준다.

이렇게 최소 횟수를 찾으면 된다.

 

<전체코드>

import java.util.*;

class Solution {
    
    static int[] dx = { 1, 0, -1, 0};
    static int[] dy = { 0, -1, 0, 1};
    static List<List<Integer>> list;
    
    static class vertex{
        int r;
        int c;
        int count;
        
        vertex(int r, int c, int count){
            this.r = r;
            this.c = c;
            this.count = count;
        }
   }
    
    public int solution(int[][] board, int r, int c) {
        int answer = Integer.MAX_VALUE;
        list = new ArrayList<List<Integer>>();
        
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0 ; i < 4 ; i++){
            for( int j = 0 ; j < 4 ; j++){
                if(board[i][j] != 0){
                    set.add(board[i][j]);
                }
            }
        }
        
        List<Integer> card = new ArrayList<Integer>();
        for(int num : set){
            card.add(num);
        }
        
        Permutation(card, new ArrayList<Integer>(), 0, card.size());
        
        for(List<Integer> order : list){
            int sum = 0;
            int[][] copyboard = copyBoard(board);
            vertex v = new vertex(r, c, 0);

            for(int cardNumber : order){
                int cnt = 0;
                v = bfs(copyboard, cardNumber, v.r, v.c);
                copyboard[v.r][v.c] = 0;
                cnt += v.count + 1;

                v = bfs(copyboard, cardNumber, v.r, v.c);
                copyboard[v.r][v.c] = 0;
                cnt += v.count + 1;

                sum += cnt;
            }

            answer = Math.min(answer, sum);
        }
      
        return answer;
    }
    
    static vertex bfs(int[][] board, int cardNumber, int r, int c){

        Queue<vertex> queue = new LinkedList<vertex>();
        queue.add(new vertex(r, c, 0));
        boolean[][] visited = new boolean[4][4];

        while(!queue.isEmpty()){

            vertex v = queue.poll();
            if(board[v.r][v.c] == cardNumber){
                return v;
            }

            for(int i = 0 ; i < 4 ; i++){

                int nr = v.r + dy[i];
                int nc = v.c + dx[i];

                if(nc < 0 || nc >= 4 || nr < 0 || nr >= 4 || visited[nr][nc]){ continue; }

                visited[nr][nc] = true;
                queue.add(new vertex(nr, nc, v.count + 1));
            }

            for(int i = 0 ; i < 4 ; i++){
                vertex nv = findCtrlMove(board, v.r, v.c, i);

                if((nv.r == v.r && nv.c == v.c) || visited[nv.r][nv.c]) {continue;}

                visited[nv.r][nv.c] = true;
                nv.count = v.count + 1;
                queue.add(nv);
            }          
        }

        return null;
    }
    
    static vertex findCtrlMove(int[][] board, int r, int c ,int direction){
        
        while(true){
            r += dy[direction];
            c += dx[direction];
            
            if(r < 0 || r >= 4 || c < 0 || c >= 4){
                r -= dy[direction];
                c -= dx[direction];
                
                break;
            }
            
            if(board[r][c] != 0){
                break;
            }   
        }
        
        return new vertex(r, c, 0);
    }
    
    static int[][] copyBoard(int[][] board){
        
        int[][] copy = new int[4][4];
        for(int i = 0 ; i < 4 ; i++){
            copy[i] = board[i].clone();
        }
        
        return copy;
    }
    
    static void Permutation(List<Integer> card, List<Integer> result, int r, int size){

        if( r == size){
            List<Integer> temp = new ArrayList<Integer>();
            for(int num : result){
                temp.add(num);
            }
            list.add(temp);            
            return;
        }

        for(int i = 0 ; i < card.size() ; i++){
            result.add(card.remove(i));
            Permutation(card, result, r + 1, size);
            card.add(i, result.remove(result.size() - 1));
        }
    }
}

진짜 다양한 알고리즘을 가지고 사고를 해야겠다.