[프로그래머스] 카드 짝 맞추기 (2021 KAKAO Blind Recruitment)

문제 링크

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

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

 

풀이

완전 탐색 문제입니다.

 

1) 게임판의 특정 칸에서 다른 임의의 칸으로 이동할 때 드는 최소 동작 횟수를 구해주는 함수를 만들어줍시다.

bfs로 한 칸짜리 4방향(↑, ↓, →, ←), 가장 가까운 카드 혹은 벽(Ctrl + ↑, ↓, →, ←)을 queue에 넣어주면서 돌리면 쉽게 구할 수 있습니다. line(17 ~ 56)

2) 어떤 순서로 카드를 없애나갈지 선택해줍니다. 순열로 돌리면 됩니다. (line 90~95)

3) 그림이 n인 두 카드를 없애야 하는 상황에서, 두 카드 중 어느 카드를 먼저 선택할지 결정해야 합니다. (line 62 ~ 67)

min( 동작 횟수[현재 커서 위치 → 카드 1 → 카드 2], 동작 횟수[현재 커서 위치 → 카드 2 →카드 1] )인 값을 취하면 됩니다.

4) 풀이 2와 3을 이용하여 가능한 모든 경우에 대한 최솟값을 반환하면 됩니다.

 

정답 코드

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ft first
#define sd second
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvb = vector<vb>;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool isValid(int x, int y){
	return 0<= x && x < 4 && 0 <= y && y < 4;
}
int getDist(const vvi &p, int sx, int sy, int ex, int ey){
	queue<pii> q;
	vvb chk(4, vb(4));
	chk[sx][sy] = true;
	q.emplace(sx, sy);
	
	int dist = 0;
	while(!q.empty()){
		int qsize = q.size();
		while(qsize--){
			auto [x, y] = q.front();
			q.pop();
			
			if(x == ex && y == ey) return dist;

			for(int k=0; k<4; k++){
				int nx = x+dx[k], ny = y+dy[k];
				if(isValid(nx, ny) && !chk[nx][ny]){
					chk[nx][ny] = true;
					q.emplace(nx, ny);
				}
				while(isValid(nx, ny) && p[nx][ny] == 0){
					nx += dx[k];
					ny += dy[k];
				}
				if(!isValid(nx, ny)){
					nx -= dx[k];
					ny -= dy[k];
				}
				if(!chk[nx][ny]){
					chk[nx][ny] = true;
					q.emplace(nx, ny);
				}
				
			}
		}
		dist++;
	}
	return dist;
}

int go(vvi &p, pii pairs[][2], const vi &cards, int i, int r, int c){
	if(i == cards.size()){
 		return 0;
	}
	int card = cards[i];
	auto [x1, y1] = pairs[card][0];
	auto [x2, y2] = pairs[card][1];
	int d1 = getDist(p, r, c, x1, y1) + getDist(p, x1, y1, x2, y2);
	int d2 = getDist(p, r, c, x2, y2) + getDist(p, x2, y2, x1, y1);
	int ret = min(d1, d2) + 2;
	p[x1][y1] = p[x2][y2] = 0;
	if(d1 < d2) ret += go(p, pairs, cards, i+1, x2, y2);
	else ret += go(p, pairs, cards, i+1, x1, y1);
	
	return ret;
}
int solution(vector<vector<int>> board, int r, int c) {
	pii pairs[10][2];
	memset(pairs, -1, sizeof(pairs));
	vi cards;
	
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			int x = board[i][j];
			if(x){
				pii tmp = pairs[x][0];
				int idx = tmp.ft != -1;
				pairs[x][idx] = {i, j};
				if(idx == 0) cards.push_back(x);
			}
		}
	}
	sort(all(cards));
	int ans = 0x3f3f3f3f;
	do {
		vvi tmp(board);
		ans = min(ans, go(tmp, pairs, cards, 0, r, c));
	} while(next_permutation(all(cards)));
	
	return ans;
}