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

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

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

2021 kakao blind recruitment 문제였다.

 

부르트포스와 bfs를 사용하여 문제를 해결하였다.

 

문제풀이: 

1. 카드의 짝 만큼 permutation을 돌린다. (next_permutation 사용)

2. 카드의 조합을 순서대로 찾아가며 bfs로 짝을 찾아 카드를 지운다.

3. 최소가 나오는 경우를 찾아야하므로 모든 경우를 다 본다.

 

만약 (1카드, 2카드, 3카드) 3종류의 카드 세트가 있다면 

순열이 (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1) 총 6개가 될것이다.

이를 토대로 전역변수로 현재 커서의 위치를 저장하면서 bfs를 돌리면서 

두 카드중 가까운카드 -> 먼 카드 순으로 돌면서 총 몇번의 명령어를 입력했는지 확인한다.

 

코드:

 

	#include <string>
	#include <vector>
	#include <algorithm>
	#include <iostream>
	#include <queue>
	using namespace std;
	vector<vector<int>> board;
	vector<int> card;
	int dx[] = {1,-1,0,0};
	int dy[] = {0,0,1,-1};
	int answer = 0x3f3f3f3f;
	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;
	int y = q.front().first.second;
	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()));
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub