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

 

* 2/22 팀즈 미팅에서 푼 문제 해설입니다!

 

해당 문제는 "프로그래머스 - [코딩테스트 연습] - 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기" 에서 풀어보실 수 있습니다.

 

문제

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

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

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

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

예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.

[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회

[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회

[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회

위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.

 

문제

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

풀이

이 문제는 무려 정답률이 0.95% 에 달하는.. 상당히 어려운 문제입니다.

2021 카카오 블라인드 채용 1차 코딩 테스트 6번으로 나왔고, 이 테스트의 합격 컷이 대략 4 솔브였던 점을 감안하면, 사실 이 문제를 꼭 풀지 않아도 통과할 수 있는 시험이었던 것 같아요

 

하지만 우리는 지금까지 배웠던 것들을 잘 활용하면 이 문제도 풀 수 있답니다!

 

우선 문제에서 필요한 지식은 총 두 가지입니다.

1. bfs

2. 백트래킹

 

1. bfs는 카드를 뒤집기 위해 최단거리로 커서를 움직이는 데에 쓰입니다. 

일반적으로 (상, 하, 좌, 우)를 움직일 때 우리는 현재 칸에서 4방향을 움직여보며 범위와 방문 횟수를 체크한 후 큐에 집어넣는다면, 이 문제에서는 ctrl + [방향키] 로 움직일 수 있다는 점을 고려해 ctrl + (상,하,좌,우) 4방향도 추가해 큐에 넣어줘야 합니다.

그렇다면 어디서 출발해 어디서 도착하는 bfs 코드를 구현해야 할까요?

여기서 우리는 간단히 게임을 상상해봅시다.

카드 종류가 1,2,3번이 있고 각 번호 당 A, B 카드로 나눌게요. 즉 카드는 총 1A, 1B, 2A, 2B, 3A, 3C 가 있습니다.

 

우리는 최단 거리로 카드를 모두 뒤집어 놔야 해요. 그렇다면 괜히 1A를 뒤집었다가 2A나 3C 같이 쌍이 맞지 않은 카드를 뒤척거릴 필요가 없습니다. 왜냐하면 문제에서 우리는 뒤집힌 카드의 번호를 모두 알고 있기 때문이죠.

 

따라서 만약 커서가 1A 위치에 있다면, 그다음엔 bfs를 이용해 1B 카드를 찾고 뒤집는 과정이 있어야 합니다.

 

우선 bfs 활용 방법은 여기까지만 하고 밑에서 종합해 설명하겠습니다.

 

2. 백트래킹은 도대체 카드를 어떤 순서로 뒤집을 것인가? 에 대한 의문을 충족시켜주기 위해 등장합니다.

위의 예시를 그대로 가져오자면 1,2,3번 카드가 있는데 1->2->3 순으로 뒤집을 것인지, 2->1->3 순으로 뒤집을 것인지에 따라 커서가 움직이는 횟수는 차이가 날 수밖에 없지요. 

만약 1번 카드 쌍이 사라진 후, 2번 카드를 뒤집을 때 bfs를 해서 나온 최단거리가

1번 카드가 그대로 있을 때 bfs를 해서 나온 최단거리보다 작다면 (ctrl 연산으로 인해) 

1번 카드를 뒤집고 2번을 뒤집는 게 더 이득일 수 있습니다. (반대로 2번에 의해 1번이 영향을 받는다면 각각 계산을 해봐야겠죠)

 

하지만 강의에서 말씀드린 것처럼, 브루트 포스, 백트래킹은 모든 순서를 다 해볼 수 있기 때문에 사전에 어떤 게 빠를지 계산하지 않고, 그냥 말 그대로 다 해봐서 더 좋은 놈 고르면 됩니다.

이건 모든 문제에서 다 적용되는 건 아니고, 항상 문제 제한을 잘 봐야 합니다.

문제에서는 총 6개의 카드 쌍이 나올 수 있기 때문에 가능한 순열은 6! 가지 겠죠.

여기서 각 카드 쌍마다 A, B 카드가 있고, 현재 커서에서 A를 뒤집고 B로 갈 것인지, 아니면 B를 먼저 뒤집고 A로 갈 것인지를 정해야 하기 때문에 또 2가지 경우가 더 붙습니다. 

여기까지 시간 복잡도는 6! x (2 ^ 6) 이 되고, 총 46080번 계산을 하게 되네요.

 

하지만 이 계산은 bfs 계산이기 때문에 bfs의 시간 복잡도를 계산하면, 총 칸 수가 4x4 = 16 칸이고

각 칸마다 최대 8개의 간선(4+4)이 포함되어 있기 때문에 bfs의 시간 복잡도는 (16 + 16x8) = 144

따라서 총 시간복잡도는 46080x144 = 6,635,620 이 되므로 이 문제는 브루트 포스로 해결 가능한 문제가 됩니다.

 

즉, 다시 한번 풀이 과정을 요약하자면

1. 우선 백트래킹을 통해 뒤집을 카드 쌍의 순서를 정해줍니다. (1->2->3, 2->1->3 등등)

2. 여기서 카드 쌍마다 A를 먼저 뒤집을지 B를 먼저 뒤집을지 정해줍니다.

3. 순서가 모두 정해졌다면, 순서대로 bfs를 통해 뒤집어줍니다. (최단거리를 구합니다.)

4. 각 순서 쌍마다 시뮬레이션을 했다면, 그중 가장 낮게 나온 최단 거리를 정답으로 출력하면 됩니다.

 

참고로 제 코드는 완벽한 코드가 아닙니다. 그 이유는.. bfs를 쓸데없이 함수 처리 안 하고 4번이나 직접 써서 그런데.. 이해하기 쉬울 것 같아서 그냥 내버려두고 올립니다 ㅎㅎ..

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int y, x; //현재 커서의 위치
int board1[10][10]; // board판
bool seq_check[10]; //순열 돌릴 때 체크 배열 
int seq[10]; //순열 저장하는 배열
int ans = 987654321;
int card_num = 0; //카드 쌍의 개수
vector<int>card; //카드 번호들 저장 배열

int dy[] = { 0, 0, 1, -1 };
int dx[] = { 1, -1, 0, 0 };
bool check[4][4]; //bfs 돌릴 때 방문 체크 배열
//(r,c) : 현재 위치, sum : 움직인 총 횟수, cnt : 몇쌍의 카드를 뒤집었는가?
void simulate(int r, int c, int sum, int cnt) {
	if (cnt == card_num) {
		ans = min(ans, sum);
		//for(int i=0; i<card_num; i++) cout<<seq[i]<<" ";
        //cout<<r<<" "<<c;
        //cout<<"\n";
        //cout<<sum<<"\n";
		return;
	}

	// 현재 seq[cnt] 의 카드를 뒤집어야 한다.
	// 한 쌍의 카드가 A,B라 할 때
	// 1. 우선 A,B 카드 위치를 구한다.
	int a_y = -1, a_x = 0, b_y = 0, b_x = 0;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (board1[i][j] == seq[cnt]) {
				if (a_y == -1) {
					a_y = i; a_x = j;
				}
				else {
					b_y = i; b_x = j;
				}
			}
		}
	}

	int to_a = 0, to_b = 0, atob = 0, btoa;

	// case1. A -> B 순으로 뒤집는 경우
	memset(check, false, sizeof(check));
	queue<tuple<int, int, int> >q;
	q.push(make_tuple(r, c, 0));
	check[r][c] = true;
	while (!q.empty()) {
		int yy, xx, move;
		tie(yy, xx, move) = q.front();
		q.pop();
		if (yy == a_y && xx == a_x) {
			to_a = move;
			break;
		}
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) continue;
			if (check[ny][nx]) continue;
			check[ny][nx] = true;
			q.push(make_tuple(ny, nx, move + 1));
		}
		//ctrl 조작 연산
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			while (0 <= ny && ny < 4 && 0 <= nx && nx < 4 && board1[ny][nx] == 0) {
				ny += dy[k];
				nx += dx[k];
			}
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
				ny -= dy[k]; nx -= dx[k];
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
			else {
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
		}
	}
    // a->b
	memset(check, false, sizeof(check));
	while (!q.empty()) q.pop();
	q.push(make_tuple(a_y, a_x, 0));
	check[a_y][a_x] = true;
	while (!q.empty()) {
		int yy, xx, move;
		tie(yy, xx, move) = q.front();
		q.pop();
		if (yy == b_y && xx == b_x) {
			atob = move;
			break;
		}
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) continue;
			if (check[ny][nx]) continue;
			check[ny][nx] = true;
			q.push(make_tuple(ny, nx, move + 1));
		}
		//ctrl 조작 연산
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			while (0 <= ny && ny < 4 && 0 <= nx && nx < 4 && board1[ny][nx] == 0) {
				ny += dy[k];
				nx += dx[k];
			}
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
				ny -= dy[k]; nx -= dx[k];
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
			else {
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
		}
	}
    

	// case2. B -> A 순으로 뒤집는 경우
	memset(check, false, sizeof(check));
	while (!q.empty()) q.pop();
	q.push(make_tuple(r, c, 0));
	check[r][c] = true;
	while (!q.empty()) {
		int yy, xx, move;
		tie(yy, xx, move) = q.front();
		q.pop();
		if (yy == b_y && xx == b_x) {
			to_b = move;
			break;
		}
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) continue;
			if (check[ny][nx]) continue;
			check[ny][nx] = true;
			q.push(make_tuple(ny, nx, move + 1));
		}
		//ctrl 조작 연산
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			while (0 <= ny && ny < 4 && 0 <= nx && nx < 4 && board1[ny][nx] == 0) {
				ny += dy[k];
				nx += dx[k];
			}
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
				ny -= dy[k]; nx -= dx[k];
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
			else {
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
		}
	}

	// b->a
	memset(check, false, sizeof(check));
	while (!q.empty()) q.pop();
	q.push(make_tuple(b_y, b_x, 0));
	check[b_y][b_x] = true;
	while (!q.empty()) {
		int yy, xx, move;
		tie(yy, xx, move) = q.front();
		q.pop();
		if (yy == a_y && xx == a_x) {
			btoa = move;
			break;
		}
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) continue;
			if (check[ny][nx]) continue;
			check[ny][nx] = true;
			q.push(make_tuple(ny, nx, move + 1));
		}
		//ctrl 조작 연산
		for (int k = 0; k < 4; k++) {
			int ny = yy + dy[k];
			int nx = xx + dx[k];
			while (0 <= ny && ny < 4 && 0 <= nx && nx < 4 && board1[ny][nx] == 0) {
				ny += dy[k];
				nx += dx[k];
			}
			if (0 > ny || ny >= 4 || 0 > nx || nx >= 4) {
				ny -= dy[k]; nx -= dx[k];
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
			else {
				if (check[ny][nx]) continue;
				check[ny][nx] = true;
				q.push(make_tuple(ny, nx, move + 1));
			}
		}
	}
	board1[a_y][a_x] = 0;
    board1[b_y][b_x] = 0;
	simulate(a_y, a_x, sum + btoa + to_b + 2, cnt + 1);
	simulate(b_y, b_x, sum + atob + to_a + 2, cnt + 1);
    board1[a_y][a_x] = seq[cnt];
	board1[b_y][b_x] = seq[cnt];
}
//순열 돌리는 함수, cnt : 현재 몇쌍의 카드를 순열에 넣었는가?
void go(int cnt) {
	if (cnt == card_num) {
		//순열이 완성되었다면, 카드 제거
		simulate(y, x, 0, 0);
		return;
	}
	else {
		for (int i = 0; i < card.size(); i++) {
			if (seq_check[card[i]]) continue;
			seq_check[card[i]] = true;
			seq[cnt] = card[i];
			go(cnt + 1);
			seq_check[card[i]] = false;
		}
	}
	return;
}

int solution(vector<vector<int>> board, int r, int c) {
	y = r; x = c;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			board1[i][j] = board[i][j];
			if (board[i][j] != 0) {
				card_num++;
				card.push_back(board[i][j]);
			}
		}
	}
	card_num /= 2;
	//카드 중복 원소 제거
	sort(card.begin(), card.end());
	card.erase(unique(card.begin(), card.end()), card.end());

	go(0);


	return ans;
}