코딩테스트 -- 카드 짝 맞추기 - (프로그래머스 / C++)

프로그래머스

 

문제!

---

게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다.
게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다.
유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.

게임에서 카드를 선택하는 방법은 다음과 같습니다.

• 카드는 커서를 이용해서 선택할 수 있습니다.
  • 커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는 "굵고 빨간 테두리 상자"를 의미합니다.
• 커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
  • 방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
  • [Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
    • 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
  • 만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
• 커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
  • [Enter] 키를 입력해서 카드를 뒤집었을 때
    • 앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
    • 앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.

"베로니"는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수 1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수 1로 계산합니다.

다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다.
아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.

 

---

요약하면 이동방법이 상하좌우 + (ctrl + 상하좌우(카드나 맵 끝까지 이동)) 이렇게 8가지 존재하는 게임에서

모든 카드를 연결하여 없애는 최소한의 키 조작 횟수를 구하는 방법!

 

처음 생각한 방법은 무작정 완전탐색입니다!

애초에 보드판이 4 * 4 밖에 되지않기에 

 

완전탐색으로도 충분한 경우의 수가 나올것 같았습니다!

 

하지만.. 벽을 만나고 찾아보니 여기서 조금더 나아가서 조합을 사용하네요....

 

조합을 어떻게?

 

만약 카드가 4종류 있다고 하면 현재위치에서 어떤 카드부터 어떤카드 순으로 짝을 맞춰줄지를 미리 정해주는 방법!

 

ex )  1234 ,  1324 , 1432 , 2341 , 3412 , 4123 등등 이러한 순서대로 짝을 맞춰본후 그중에서 가장 적은 순서로 통과하는 방법을 찾으면 끝!

 

 

조합을 하기위해서는 저번에도 한번 사용해보긴했는데

next_permutation(card.begin(),card.end())

 이 함수를 사용하면 card안의 모든 숫자의 조합을 계산해 출력해준다고 합니다!

 

 

그럼 시작!

 

 

먼저 시작하기전에 보드와 카드들, 이동 방향? 등을 선언해주고

vector<vector<int>> board;
vector<int> card;
int dy[] = {-1,1,0,0};// 상하좌우
int dx[] = {0,0,-1,1};

int answer = 987654321;
int r,c;

 

 

총 8종류의 카드중 어떤것들이 있는지 찾고 card배열에 넣어줍시다.

int solution(vector<vector<int>> b, int rr, int cc) {
    bool card_check[7] = {0,};// 카드가 있는지?
    
    for(int i=0;i<b.size();i++){
        for(int j=0;j<b[i].size();j++){
            if(b[i][j]){//카드 체크
                card_check[b[i][j]] = true;
            }
        }      
    }
        
    for(int i=1;i<7;i++){
        if(card_check[i]){// 있는 카드만 체크
            card.push_back(i);
        }
    }

 

그러고 나서 탐색을 하는데 여기서 

아래 방법을 통해 조합을 만들어 반복 탐색되도록 만들어 줍시다.

do{
        ////~~~~~
    }while(next_permutation(card.begin(),card.end())); //조합..!!!   2134 2143

 

그러면 아래처럼 만들어집니다.

do{
        board = b;
        r = rr, c = cc;
        int tmp = 0;
        for(int i=0;i<card.size();i++){// 탐색 시작!
            tmp += bfs(card[i]);// 가까운 하나
            tmp += bfs(card[i]);//남은하나
        }
        answer = min(answer,tmp);
    }while(next_permutation(card.begin(),card.end())); //조합..!!!   2134 2143

 왜 bfs가 두번? >> 현재위치에서 가까운 카드 i 를 먼저 찾고 그다음 카드를 찾기 위해!

(찾고나면 board에서 그자리르 0 으로 처리해버림!)

 

 

 

 

이제 본격적인 bfs 탐색 함수를이용해서 만들어 봅시다.

 

가장 먼저 고려해줘야할것은 한칸씩 움직이는것과 계속 쭉 이동하는 방법 >> 이 두 부분은 나눠서 따로 진행시켜주고

계속 이동하는 값을 queue에 저장하고, 불러오며  이동해줍시다. (현재 찾고있는카드 dest를 찾을때까지 반복!)

int bfs(int dest){
    bool check[4][4] = {0};
    
    queue<pair<pair<int,int>,int>> q;// 현재위치 파악
    
    q.push({{r,c},0});
    
    check[r][c] = true;
    
    while(!q.empty()){//저장한 값이 있다면? 
        int x = q.front().first.first;//x좌표
        int y = q.front().first.second;//y좌표
        int cnt = q.front().second;//현재까지의 이동값
        q.pop();
        
        if(board[x][y] == dest){// 목적지 카드 발견! // 찾을때까지
            board[x][y] = 0;
            r = x, c = y;
            return cnt+1;
        }
        
        for(int i=0;i<4;i++){// 한칸이동
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4){// 범위가 넘칠때 멈추기
                continue;
            }
                
            if(!check[nx][ny]){// 온적이 없다면
                check[nx][ny] = true;
                q.push({{nx,ny},cnt+1});// 계속이동
            }
        }
        
        for(int i=0;i<4;i++){ // 싹다 이동
            int nx = x;
            int ny = y;
           	while(nx+dx[i]>=0&&ny+dy[i]>=0&&nx+dx[i]<4&&ny+dy[i]<4){// 계속 직진
                nx += dx[i];
                ny += dy[i];
                
                if(board[nx][ny]){// 카드가 있다면 멈춤
                    break;
                }
            } 
            
            if(!check[nx][ny]){
                check[nx][ny] = true;
                q.push({{nx,ny},cnt+1});
            }
        }
    }
}

 

 

여기 까지네요 제가 코드를 직접 짜보다가 먼가 많이 엉켜서 포기하고 찾아보았습니다....

 

 

프로그래머스 - 카드 짝 맞추기 / C++

 

 

머리좀 식히고 다시한번 해보겠습니다!

 

 

ALL

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

vector<vector<int>> board;
vector<int> card;
int dy[] = {-1,1,0,0};// 상하좌우
int dx[] = {0,0,-1,1};

int answer = 987654321;
int r,c;

int bfs(int dest){
    bool check[4][4] = {0};
    
    queue<pair<pair<int,int>,int>> q;// 현재위치 파악
    
    q.push({{r,c},0});
    
    check[r][c] = true;
    
    while(!q.empty()){//저장한 값이 있다면? 
        int x = q.front().first.first;//x좌표
        int y = q.front().first.second;//y좌표
        int cnt = q.front().second;//현재까지의 이동값
        q.pop();
        
        if(board[x][y] == dest){// 목적지 카드 발견! // 찾을때까지
            board[x][y] = 0;
            r = x, c = y;
            return cnt+1;
        }
        
        for(int i=0;i<4;i++){// 한칸이동
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4){// 범위가 넘칠때 멈추기
                continue;
            }
                
            if(!check[nx][ny]){// 온적이 없다면
                check[nx][ny] = true;
                q.push({{nx,ny},cnt+1});// 계속이동
            }
        }
        
        for(int i=0;i<4;i++){ // 싹다 이동
            int nx = x;
            int ny = y;
           	while(nx+dx[i]>=0&&ny+dy[i]>=0&&nx+dx[i]<4&&ny+dy[i]<4){// 계속 직진
                nx += dx[i];
                ny += dy[i];
                
                if(board[nx][ny]){// 카드가 있다면 멈춤
                    break;
                }
            } 
            
            if(!check[nx][ny]){
                check[nx][ny] = true;
                q.push({{nx,ny},cnt+1});
            }
        }
    }
}

int solution(vector<vector<int>> b, int rr, int cc) {
    bool card_check[7] = {0,};// 카드가 있는지?
    
    for(int i=0;i<b.size();i++){
        for(int j=0;j<b[i].size();j++){
            if(b[i][j]){//카드 체크
                card_check[b[i][j]] = true;
            }
        }      
    }
        
    for(int i=1;i<7;i++){
        if(card_check[i]){// 있는 카드만 체크
            card.push_back(i);
        }
    }
        
    
    do{
        board = b;
        r = rr, c = cc;
        int tmp = 0;
        for(int i=0;i<card.size();i++){// 탐색 시작!
            tmp += bfs(card[i]);// 가까운 하나
            tmp += bfs(card[i]);//남은하나
        }
        answer = min(answer,tmp);
    }while(next_permutation(card.begin(),card.end())); //조합..!!!   2134 2143
    
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!