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

문제 링크

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

프로그래머스

카드 뒤집기 게임에서 모든 카드의 짝을 맞추는 데 필요한 최소 커서 이동 횟수를 리턴하자.

 

풀이

어디에 어떤 카드가 있는 지는 이미 알고 있지만, 어떤 카드부터 뒤집어야 가장 적은 횟수로 모든 카드의 짝을 맞출 수 있는 지는 알 수 없다.

그렇기 때문에 모든 경우의 수를 다 해보고 최소 횟수를 구해준다.

보드가 4 X 4 크기로 그리 크지 않기 때문에 모든 경우를 다 해봐도 시간초과가 나지 않는다.

 

next_permuation() 함수를 이용해서 카드 뒤집는 순서를 정해서 모든 경우의 수를 다 해볼 수 있도록 한다.

카드가 1, 2, 3 세 종류가 있다고 하자. 만약 순열을 통해 나온 순서가 2, 1, 3 이면

2번, 1번, 3번 카드 순서대로 짝을 맞춰준다.

 

현재 커서 위치에서 원하는 번호의 카드까지 이동 횟수는 bfs탐색을 이용해서 찾는다.

이동할 수 있는 경우의 수는 최대 8가지로

←, ↑, ↓, → : 상하좌우 1칸씩 이동 (4가지)

[Ctrl]  +  ←, ↑, ↓, →  : 상하좌우 여러칸 이동(4가지)

원하는 카드를 발견하면 그 즉시 탐색을 종료하고 이동 횟수를 리턴한다.

이때 Enter키를 누르는 것까지 생각 해야하기 때문에, 탐색해서 찾은 이동 횟수에 + 1을 해서 리턴해준다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
pair<int,int> cursor;
vector<vector<int>> Board;
bool visited[5][5];
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};
 
bool is_ok(pair<int,int> pos){
    if(pos.first < 0 || pos.first >= 4 || pos.second < 0 || pos.second >= 4)
        return false;
    return true;
}
 
int bfs(int ed){
    queue<pair<pair<int,int>,int>> q;
    q.push({cursor, 0});
    memset(visited, false, sizeof(visited));
    
    while(!q.empty()){
        pair<int,int> now = q.front().first;
        int move = q.front().second;
        q.pop();
        if(visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        
        if(Board[now.first][now.second] == ed){
            cursor = now;
            Board[cursor.first][cursor.second] = 0;
            return move + 1; // + Enter
        }
        
        for(int i = 0; i<4; i++){ //1칸씩 이동
            pair<int,int> next = {now.first + dy[i], now.second + dx[i]};
            if(is_ok(next) && !visited[next.first][next.second])
                q.push({next, move + 1});
        }
        
        for(int i = 0; i<4; i++){//ctrl로 이동
            pair<int,int> next = {now.first, now.second};
            while(is_ok({next.first + dy[i], next.second + dx[i]})){
                next.first += dy[i];
                next.second += dx[i];
                if(Board[next.first][next.second] && !visited[next.first][next.second])
                    break;
            }
            q.push({next, move + 1});
        }
        
    }
}
 
 
int solution(vector<vector<int>> board, int r, int c) {
    int answer = 987654321;
    vector<int> cards;
    for(auto v : board)
        for(auto i : v)
            if(i) cards.push_back(i);
    
    sort(cards.begin(), cards.end());
    cards.erase(unique(cards.begin(), cards.end()), cards.end());
    
    do{
        cursor = {r, c};
        Board = board;
        int temp = 0;
        for(auto card : cards){
            temp += bfs(card);
            temp += bfs(card);
        }
        answer = min(temp, answer);
    }while(next_permutation(cards.begin(), cards.end()));
    
    return answer;
}