[ 프로그래머스 카드 짝 맞추기 (Lv3) ] (C++)

프로그래머스의 카드 짝 맞추기(Lv3) 문제이다.

 

[ 문제풀이 ]

주어진 맵에 카드를 모두 짝에 맞게 제거하기 위한 키 조작 횟수의 최솟값을 구해야 하는 문제이다.

단계별로 문제를 접근해보자.

 

#1. 전체적인 접근

먼저 가장 첫 번째 단계로 어떤 것을 할 것이다 라는 이야기 보다는 전체적으로 문제를 확인하고 어떻게 접근할것인지에 대해서 이야기를 해보자. 그리고 이를 통해서 우리가 미리 가지고 있어야 할 정보들은 어떤 것들이 있는지 부터 알아보자.

1 - 1) 맵에는 카드들이 존재한다.

너무나도 간단한 이야기이지만, 본인은 여기서 다음과 같은 정보를 저장해 주었다.

그럼 맵을 탐색했더니 존재하는 카드가 { A , B , C } 가 있었다고 가정해보자.

A의 모양을 한 카드가 2장, B의 모양을 한 카드가 2장, C의 모양을 한 카드가 3장이 있는 상태인 것이다.

이 때 우리가 이 카드를 모두 뒤집는 방법으로는 다음과 같은 방법들이 있을 것이다.

방법1 : 현재위치 - A - B - C

방법2 : 현재위치 - A - C - B

방법3 : 현재위치 - B - A - C

.....

방법K : 현재위치 - C - B - A

뭐 위와 같은 방법들이 있을 것이다. 즉 ! 존재하는 카드들을 어떤 순서로 탐색하는지에 따라서 결과가 달라질 수 있다는 것이다. 여기서 "존재하는 카드들"에는 무엇이 있는지를 파악해 주어야 한다.

문제에서 반드시 카드가 오름차순으로 주어진다는 말은 없다. 즉 ! 카드가 3쌍이 존재한다면, 이 3쌍은 반드시 { 1 , 2 , 3} 이 아닌 { 1 , 4 , 6 } 과 같은 형태로 주어질 수도 있다는 것이다. 그럼 이 맵에 존재하는 카드들을 어떻게 관리하는지는 밑에서 더욱 구체적으로 알아보도록 하고 여기서는 이러한 정보들이 있구나 정도로만 넘어가 보도록 하자.

1 - 2) 맵에서 같은 모양의 카드는 2장씩 존재한다.

이 문제에서 등장하는 맵에서는 총 6가지의 카드가 발생할 수 있다.(맵의 원소는 0이상 6이하인 자연수)

그리고 우리는 이 상황속에서 우리는 최소의 조작 횟수로 카드를 짝에 맞춰 제거해주어야 한다.

그렇다면 맵에서 A1과 A2 가 존재한다고 가정해보자. 그리고 A1과 A2는 A라는 서로 같은 카드라고 가정을 해보자.

그럼 ! 우리는 현재위치에서 A를 뒤집기 위해서 2가지 방법이 있을 것이다.

방법1 : 현재위치 - A1 - A2

방법2 : 현재위치 - A2 - A1

이렇게 2가지 방법이 있을 것이다. 한 쌍의 카드 중 어떤 카드를 먼저 찾아갈지에 따라서 조작 횟수가 달라질 수 있다.

 

그럼 이제 이 방법들에 대해서 구체적으로 이야기를 해보자.

#2. 존재하는 카드들에 대한 관리

그럼 1-1)에서 이야기 했던 "존재하는 카드"들에 대한 관리를 먼저 해보자.

우리는 맵에 어떤 카드들이 존재하는지를 먼저 파악해 주어야 한다. 본인은 하나의 벡터를 만들어서 존재하는 카드들만 따로 저장을 해서 만들어 주었다. 간단한 과정이니 코드로 바로 확인해보자.

void Find_Exist_Card(vector<vector<int>> board)
{
	vector<bool> Exist(CARD_MAX, false);
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board.size(); j++)
		{
			if (board[i][j] == 0) continue;
			if (Exist[board[i][j]] == false)
			{
				Exist[board[i][j]] = true;
				Card_List.push_back(board[i][j]);
			}
		}
	}
}

Card_List라는 Vector에 존재하는 카드 숫자들만 저장을 해놓는 코드이다.

이 Vector가 어떻게 사용되는지는 밑에서 구체적으로 확인해보자.

 

#3. 카드들의 위치

1-2)에서 'A'라는 카드를 뒤집기 위해서 현재 위치에서 A1을 먼저 찾은 후, A2로 넘어갈지, 아니면 반대로 A2를 먼저 찾은 후 A1으로 넘어가는지에 따라서 조작 횟수가 달라질 수 있다고 했다.

그럼 여기서, 현재위치에서 A1으로 가는 상황이든, A2로 가는 상황이든 공통적으로 필요한 정보는 뭐가 있을까 ??

바로 A1과 A2가 어느 좌표에 위치했는지에 대한 카드의 위치에 대한 정보가 필요하다.

그렇다면 'A'라는 카드에는 총 2개의 위치 정보가 있을 것이다. 바로 A1의 위치와 A2의 위치 !

그래서 본인은 이를 벡터배열을 하나 만들어서 따로 저장해 주었다.

void Find_Card_Pos(vector<vector<int>> board)
{
	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board.size(); j++)
		{
			if (board[i][j] == 0) continue;
			Card_Pos[board[i][j]].push_back(make_pair(i, j));
		}
	}
}

Card_Pos가 위치를 저장하기 위한 벡터 배열이다. Card_Pos[A] = { { x , y } , { xx , yy } } 의 의미는

A의 위치는 { x , y } 와 { xx , yy } 입니다를 의미하는 것이다.

그리고 한 카드당 같은 카드가 2장씩 존재하므로, 각 인덱스에 해당하는 벡터의 크기는 '2'가 될 것이다.

이 의미에 대해서는 밑에서 조금 더 구체적으로 이야기해보자.

 

#4. 순열 구현

이제 본격적으로 카드를 찾고 제거하는 과정으로 넘어가보자.

본인이 가장 먼저 생각했던 과정은 "순열을 구현하는 것" 이였다.

순열을 왜 구현해야 할까 ?? 어떤 카드를 먼저 뒤집는지에 따라서 그 결과가 달라지기 때문이다.

예를 들어서 맵에 존재하는 카드가 [ A , B , C ] 라고 했을 때, A를 가장 먼저 제거하고 B를 제거하고 C를 제거하는 것과 C를 가장 먼저 제거하고 B를 제거하고 A를 제거하는 것은 조작하는 횟수가 달라질 것이다.

즉 ! 어떤 카드를 먼저 제거할지, 순서에 따라서 그 결과가 달라지기 때문에 순열을 구현해 주었다.

아직 순열에 대해서 모른다면 아래의 글을 읽고 오도록 하자.

[ 순열에 대해 알아보기(Click) ]

우리는 이 순열을 구현함으로써 "카드를 어떤 순서로 제거할지" 에 대해서 정할 수가 있다.

본인은 다음과 같이 구현해 보았다.

void Setting_Search_Card_Order(int Cnt, vector<vector<int>> MAP, int r, int c, int &answer)
{
	if (Cnt == Card_List.size())
	{
		Setting_Search_SameCard_Order(0, MAP, r, c, answer);
		return;
	}

	for (int i = 0; i < Card_List.size(); i++)
	{
		if (Select[i] == true) continue;
		Select[i] = true;
		Card_Order.push_back(Card_List[i]);
		Setting_Search_Card_Order(Cnt + 1, MAP, r, c, answer);
		Card_Order.pop_back();
		Select[i] = false;
	}
}

#2에서 만들어 놓은 존재하는 카드들을 저장해놓은 "Card_List"를 탐색하면서 순열을 만드는 과정이다.

Card_Order라는 Vector에 실제로 탐색할 카드의 순서들을 저장해 주었다.

 

#5. 중복순열 구현

#4의 과정에서 우리는 주어진 카드가 [ A , B , C ] 였다면, A를 가장 먼저 제거하고, 그 다음 B를 제거한 후 마지막으로 C를 제거할지 아니면 C를 가장 먼저 제거하고 그 다음 B를 제거한 후 마지막으로 A를 제거할지와 같이 주어진 카드들을 어떤 순서대로 제거할지를 정해주었다.

그렇다면 그 다음 단계는 무엇일까 ??? 이제는 해당 카드가 가지고 있는 2장의 카드 중 어떤 카드를 먼저 제거할지에 대한 순서를 정해주는 것이다.

예를 들어서 #4의 과정으로 A - B - C로 제거 순서를 정했다면 이를 조금 더 구체적으로

A1 - A2 - B1 - B2 - C1 - C2 혹은 A2 - A1 - B1 - B2 - C2 - C1 이런식으로 주어진 카드들이 가지고 있는 2장의 카드 중 어떤 카드를 먼저 제거할지에 대해서 정해주어야 한다.

그럼 이는 어떻게 구현할 수 있을까 ??? 카드가 3장이라면 총 6개에 대한 순서를 정해주어야 하는데... 그 6개의 순서도 1번과 2번 중에서만 골라서 구현을 해야하고... 6개 중에서도 [ 1 , 2 ]번 [ 3 , 4 ] 번 [ 5 , 6 ] 번은 반드시 서로 반대되는 값을 가지고 있어야 하고.... 뭔가 복잡해 보일 수 있다.

하지만 매우 간단하게 구할수가 있다. 바로 중복순열을 이용해서 구현하는 것이다.

그리고 각 카드들 중에서 먼저 탐색할 카드만 정해주면 된다. 왜냐하면 나머지 카드 한 장은 자동적으로 설정이 되기 때문이다.

예를 들어보자. 내가 A라는 카드를 탐색할 건데, A1을 먼저 탐색한다고 설정했다고 가정해보자. 그럼 그 다음은 ? 자연스럽게 A2를 탐색하게 될 것이다. A1 이후에 또 A1을 탐색한다는 것은 말이 안되기 때문이다.

그래서 본인은 ! "순서를 정해놓은 카드들 중에서, 먼저 탐색할 카드들의 번호만 저장" 해 주었다.

카드들의 번호라는게 무엇을 의미할까 ?? 바로 Index번호를 의미한다. 무슨 Index번호일까 ??

#3에서 우리는 카드들의 위치를 Card_Pos[] 라는 Vector 배열에 저장해 주었다. 그리고 아까 잠시 이야기한 것이지만,

이 각각의 인덱스들이 가지는 벡터들은 크기가 '2'일 것이라고 이야기를 했었다.

즉, Card_Pos[A]의 크기도 '2'일 것이고, Card_Pos[B]의 크기도 '2'일 것이고, Card_Pos[C]의 크기도 '2'일 것이다.

벡터의 크기가 '2'라면 실제로 그 Index번호는 0과 1로 이루어져 있을 것이다.

다시 말해서 Card_Pos[A][0]에는 A1의 위치가, Card_Pos[A][1] 에는 A2의 위치가 저장되어 있을 것이다.

그렇다면 다시 돌아와서 중복순열에 대한 이야기를 해보자.

우리는 지금부터 3장의 카드가 있다면 0과 1 2개로만 중복순열로 3개를 만들 것이다.

그럼 예를들어서 [ 0 , 0 , 0 ] 을 만들었다고 가정해보자. 그럼 이게 무슨 의미일까 ??

내가 #4의 과정에서 카드를 뽑을 순서를 [ A , B , C ]로 정했고 이후 #5의 과정을 통해서 [ 0 , 0 , 0 ] 을 뽑았다면

결국 이는 A1 - A2 - B1 - B2 - C1 - C2 순서로 탐색하겠다는 것을 의미한다.

만약, [ A , B , C ]로 정했고 [ 0 , 1 , 1 ] 을 뽑았다면 결국 이는 A1 - A2 - B2 - B1 - C2 - C1 순서로 탐색을 하겠다는 것을 의미한다. 따라서 중복순열로 이 순서를 표현해줄 수가 있다.

그럼 중복순열을 구현한 이유에 대해서 보다 구체적으로 알아보자.

가장 먼저, 순열을 구현하기 해야 할 것이다. 왜냐하면 A1 - A2 - B1 - B2를 탐색할 때와 A2 - A1 - B1 - B2를 탐색할 때 조작횟수는 달라질 것이므로 순서에 따라 결과가 달라지므로 순열을 구현해 주어야 한다.

하지만 ! A1 - A2 를 탐색한다고 해서 그 이후에 B1 - B2를 탐색을 못하는 것은 아니다. A1 - A2를 탐색했다고 해서  B를 탐색할때는 반드시 B2 - B1를 탐색해야할까 ?? 상관없이 똑같이 1번 카드를 먼저 탐색 후 2번 카드를 탐색해도 상관이 없다. 즉 ! 1번 카드를 먼저 제거할지 2번카드를 먼저 제거할지에 대한 부분은 각 카드별로 중복적으로 선택이 가능해야 한다. 따라서 중복순열을 이용해서 이를 구현해 주었다.

아직 중복순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 중복순열에 대해 알아보기(Click) ]

본인은 다음과 같이 코드로 구현하였다.

void Setting_Search_SameCard_Order(int Cnt, vector<vector<int>> MAP, int r, int c, int &answer)
{
	if (Cnt == Card_List.size())
	{
		int Result = 0;
		int Sx = r;
		int Sy = c;
		vector<vector<int>> T_MAP = MAP;
		for (int i = 0; i < Card_List.size(); i++)
		{
			int Card = Card_Order[i];
			int Idx = SameCard_Order[i];
			Result += BFS(Sx, Sy, 0, Card, Idx, T_MAP);
			
			Sx = Card_Pos[Card][!Idx].first;
			Sy = Card_Pos[Card][!Idx].second;
		}
		answer = Min(answer, Result);
		return;
	}
	
	for (int i = 0; i < 2; i++)
	{
		SameCard_Order.push_back(i);
		Setting_Search_SameCard_Order(Cnt + 1, MAP, r, c, answer);
		SameCard_Order.pop_back();
	}
}

0과 1 2개의 값을 가지고 주어진 카드의 갯수만큼 중복순열로 뽑는 과정이다.

SameCard_Order라는 변수에 그 순서를 저장해 주는 것이다.

 

#6. 거리 구하기

이제 카드를 어떤 순서로 제거할지, 그리고 그 카드가 가지고 있는 2장의 카드 중 어떤 카드를 먼저 제거할지까지 모든 순서를 다 정해놓은 상황이다. 이제 실제로 제거를 해보면서 그 거리만 확인을 해주면 된다.

본인은 이 과정을 BFS탐색을 통해서 진행해 주었다.

BFS 탐색은 (시작점 x, 시작점 y) 에서 (카드가 있는 점 x, 카드가 있는 점 y)로 가는 최단경로를 탐색하는 방식으로 구현을 해 주었다. 물론 ! 카드가 2장씩 있기 때문에 한 장의 카드를 찾는다면, BFS 함수를 재귀호출을 통해서 그 다음 카드를 찾도록 구현을 해 주었다. 그리고 2장을 모두 찾았다면 그대로 함수를 종료해 주었다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>
 
#define MAX 4
#define CARD_MAX 7
#define INF 987654321
using namespace std;
 
vector<bool> Select(CARD_MAX, false);
vector<int> Card_List;
vector<int> Card_Order;
vector<int> SameCard_Order;
vector<pair<int, int>> Card_Pos[CARD_MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Find_Exist_Card(vector<vector<int>> board)
{
    vector<bool> Exist(CARD_MAX, false);
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board.size(); j++)
        {
            if (board[i][j] == 0) continue;
            if (Exist[board[i][j]] == false)
            {
                Exist[board[i][j]] = true;
                Card_List.push_back(board[i][j]);
            }
        }
    }
}
 
void Find_Card_Pos(vector<vector<int>> board)
{
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board.size(); j++)
        {
            if (board[i][j] == 0) continue;
            Card_Pos[board[i][j]].push_back(make_pair(i, j));
        }
    }
}
 
int BFS(int Sx, int Sy, int Find_Cnt, int Card, int Idx, vector<vector<int>> &MAP)
{
    if (Find_Cnt == 2) return 0;
    
    queue<pair<pair<int, int>, int>> Q;
    vector<vector<bool>> Visit(MAP.size(), vector<bool>(MAP.size(), false));
    Q.push(make_pair(make_pair(Sx, Sy), 0));
    Visit[Sx][Sy] = true;
    
    int Ex, Ey;
    if (Find_Cnt == 0)
    {
        Ex = Card_Pos[Card][Idx].first;
        Ey = Card_Pos[Card][Idx].second;
    }
    else
    {
        Ex = Card_Pos[Card][!Idx].first;
        Ey = Card_Pos[Card][!Idx].second;
    }
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == Ex && y == Ey)
        {
            MAP[x][y] = 0;
            Cnt += BFS(x, y, Find_Cnt + 1, Card, Idx, MAP);
            return Cnt;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX)
            {
                if (Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
        
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            while (1)
            {
                if (nx < 0 || ny < 0 || nx >= MAX || ny >= MAX)
                {
                    nx -= dx[i];
                    ny -= dy[i];
                    break;
                }
                if (MAP[nx][ny] != 0) break;
                nx += dx[i];
                ny += dy[i];
            }
 
            if (Visit[nx][ny] == false)
            {
                Visit[nx][ny] = true;
                Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
            }
        }
    }
}
 
void Setting_Search_SameCard_Order(int Cnt, vector<vector<int>> MAP, int r, int c, int &answer)
{
    if (Cnt == Card_List.size())
    {
        int Result = 0;
        int Sx = r;
        int Sy = c;
        vector<vector<int>> T_MAP = MAP;
        for (int i = 0; i < Card_List.size(); i++)
        {
            int Card = Card_Order[i];
            int Idx = SameCard_Order[i];
            Result += BFS(Sx, Sy, 0, Card, Idx, T_MAP);
            
            Sx = Card_Pos[Card][!Idx].first;
            Sy = Card_Pos[Card][!Idx].second;
        }
        answer = Min(answer, Result);
        return;
    }
    
    for (int i = 0; i < 2; i++)
    {
        SameCard_Order.push_back(i);
        Setting_Search_SameCard_Order(Cnt + 1, MAP, r, c, answer);
        SameCard_Order.pop_back();
    }
}
 
void Setting_Search_Card_Order(int Cnt, vector<vector<int>> MAP, int r, int c, int &answer)
{
    if (Cnt == Card_List.size())
    {
        Setting_Search_SameCard_Order(0, MAP, r, c, answer);
        return;
    }
 
    for (int i = 0; i < Card_List.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Card_Order.push_back(Card_List[i]);
        Setting_Search_Card_Order(Cnt + 1, MAP, r, c, answer);
        Card_Order.pop_back();
        Select[i] = false;
    }
}
 
int solution(vector<vector<int>> board, int r, int c) 
{
    int answer = INF;
    Find_Exist_Card(board);
    Find_Card_Pos(board);
    Setting_Search_Card_Order(0, board, r, c, answer);
    answer += (Card_List.size() * 2);
    return answer;
}