[프로그래머스 2021 KAKAO BLIND RECRUITMENT] 카드 짝 맞추기

문제

programmers.co.kr/learn/courses/30/lessons/72415

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

 

풀이

0. 어떤 종류의 카드를 제거한다고 할 때, 종류가 같은 카드 두 개를 찾으려고 매번 맵 전체를 순회하지않기 위해 카드의 종류별로 두 카드의 위치를 담아줍니다. [ line 86 ]

 

1. 모든 카드를 종류별로 제거해야하고 그 순서에 따라 움직이는 거리가 달라지기에 제거할 종류들의 순서를 next_permutation으로 구해줍니다. [ line 99 ~ 103 ]

 

2. 종류별로 제거한다고 할 때, 두 카드중 어떤 카드를 먼저 제거할지에 따라서도 움직이는 거리가 달라지고, 카드종류의 개수가 최대 6개이므로 모든 카드의 종류를 1번째 위치부터 탐색할지 2번째 위치부터 탐색할지 정해주는 완전탐색을 구현해줍니다. [ line 64 ~77 ]

 

3. 이제 찾아야할 카드의 종류, 두 가지중 먼저 찾을 순서까지 정해놨으므로 문제에서 정의한 이동방식을 bfs로 구현하여 움직이는 거리의 최소 값을 갱신해갑니다. [ line 18 ~62 ]

 

4. 결과적으로 시간복잡도는 $O(6! * 2^6 * 4^2)$ 정도로 해결할 수 있습니다.

 

코드

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

#define all(x) (x).begin(),(x).end()
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int board[4][4], copy_board[4][4], l, ans, dist[4][4];
vector<int> card_number, p;
vector<pii> pos[9];
pii cursor, copy_cursor;

bool isrange(int r, int c) {
	if (r < 0 || r >= 4 || c < 0 || c >= 4) return 0;
	return 1;
}

int go(int idx) {
	int kind = card_number[idx]; // 현재 뒤집을 카드의 종류
	int seq = p[idx]; // 2가지 카드중 먼저 고를 카드
	int cr, cc, nr, nc, ret = 0;
	pii tar[2] = { pos[kind][seq],pos[kind][1 - seq] }; // 뽑아야하는 카드의 순서
	for (int i = 0; i < 2; i++) {
		queue<pii> q;
		q.push({ cursor.first,cursor.second });
		memset(dist, inf, sizeof(dist));
		dist[cursor.first][cursor.second] = 0;
		while (!q.empty()) {
			tie(cr, cc) = q.front(); q.pop();

			// 뽑아야하는 카드를 찾았을 때 (최단경로)
			if (cr == tar[i].first && cc == tar[i].second) {
				cursor = tar[i]; // 커서 옮기기
				board[cr][cc] = 0; // 해당 칸 뒤집기
				if (i == 0) {
					ret = dist[cr][cc]; // 첫 번째 카드까지 찾는 비용을 저장해줌
					break;
				}
				else return ret + dist[cr][cc]; // 첫 번째 카드찾는 비용 + 두 번째 카드찾는 비용
			}

			for (int j = 0; j < 4; j++) {
				nr = cr + dir[j][0], nc = cc + dir[j][1];
				if (!isrange(nr, nc)) continue;

				// #1. 한 칸 이동
				if (dist[cr][cc] + 1 < dist[nr][nc]) {
					dist[nr][nc] = dist[cr][cc] + 1;
					q.push({ nr,nc });
				}

				// #2. Ctrl + 방향키
				while (isrange(nr, nc) && !board[nr][nc]) nr += dir[j][0], nc += dir[j][1];
				if (!isrange(nr, nc)) nr -= dir[j][0], nc -= dir[j][1];
				if (dist[cr][cc] + 1 < dist[nr][nc]) {
					dist[nr][nc] = dist[cr][cc] + 1;
					q.push({ nr,nc });
				}
			}
		}
	}
}

void comb(int idx) {
	if (idx == l) {
		int ret = 0;
		for (int i = 0; i < card_number.size(); i++)
			ret += (go(i) + 2); // 카드를 찾는 것과 별개로 enter치는건 항상 2개씩이니 이는 따로 더해줌
		ans = min(ans, ret);
		return;
	}
	for (int i = 0; i < 2; i++) {
		p.emplace_back(i);
		comb(idx + 1);
		p.pop_back();
	}
}

int solution(vector<vector<int>> Board, int r, int c) {
	ans = inf;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++) {
			board[i][j] = Board[i][j];
			if (board[i][j]) {
				card_number.emplace_back(board[i][j]);
				pos[board[i][j]].push_back({ i,j }); // 같은 카드의 위치를 저장해둠
			}
		}

	// 현재 보드에서 존재하는 카드들의 종류를 저장 후 중복 제거
	sort(all(card_number));
	card_number.erase(unique(all(card_number)), card_number.end());

	// 초기 상태 저장
	memcpy(copy_board, board, sizeof(copy_board));
	cursor = copy_cursor = { r, c };

	l = card_number.size();
	do {
		memcpy(board, copy_board, sizeof(board)); // 보드를 다시 초기상태로
		cursor = copy_cursor; // 커서를 다시 초기상태로 
		comb(0); // 현재 카드의 순서에서 i번째 카드종류 v[i]를 뽑을 때 존재하는 두가지 경우에 대해 모두 탐색
	} while (next_permutation(all(card_number))); // 제거할 카드 종류들의 순서를 모두 탐색
	return ans;
}