카드 짝 맞추기 C++

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

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

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
struct Number { int x, y; };
vector<Number> v[7];
int sz = 0;
int answer = 987654321;
int R, C;
struct Move { int x, y; };
Move mv[4] = { { 0,-1 },{ -1,0 },{ 1,0 },{ 0,1 } };
vector<vector<int>> b;
vector<int> chc;

int FindPath(int si, int sj, int  ei, int ej) {
	int visited[4][4];
	memset(visited, -1, sizeof(visited));
	queue<pair<pair<int, int>, int>> q;
	int count = 987654321;

	q.push(make_pair(make_pair(si, sj), 0));
	visited[si][sj] = 1;
	while (!q.empty()) {
		int ii = q.front().first.first;
		int jj = q.front().first.second;
		visited[ii][jj] = 1;
		int c = q.front().second;
		q.pop();

		if (ei == ii && ej == jj) {
			count = min(count, c);
			break;
		}

		for (int k = 0; k < 4; k++) {
			int movei = ii + mv[k].x;
			int movej = jj + mv[k].y;

			if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4) {
				if (visited[movei][movej] == -1) {
					q.push(make_pair(make_pair(movei, movej), c + 1));
					visited[movei][movej] = 1;
				}
				if (b[movei][movej] != 0) continue;

				bool flag = false;
				int i = movei;
				int j = movej;

				for (; i >= 0 && i < 4 && j >= 0 && j < 4; i += mv[k].x, j += mv[k].y) {
					if (b[i][j] != 0) {
						flag = true;
						if (visited[i][j] == -1) {
							visited[i][j] = 1;
							q.push(make_pair(make_pair(i, j), c + 1));
						}
						break;
					}
				}
				if (flag == false) {//좌, 위, 아래, 오른쪽
					if (k == 0)	movej = 0;
					else if (k == 1)	movei = 0;
					else if (k == 2)	movei = 3;
					else if (k == 3)	movej = 3;
					if (visited[movei][movej] == -1) {
						q.push(make_pair(make_pair(movei, movej), c + 1));
					}
				}
			}
		}
	}
	return count;
}

void FindShortest(vector<pair<int, int>> seq) {
	int tmp = 0;
	int curi = R;
	int curj = C;
	int movei, movej;
	int board_copy[4][4];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			board_copy[i][j] = b[i][j];
		}
	}

	b[curi][curj] = 0;
	for (int i = 0; i<seq.size(); i++) {
		movei = seq[i].first;
		movej = seq[i].second;
		int t = FindPath(curi, curj, movei, movej);
		b[movei][movej] = 0;
		tmp += (t + 1);
		curi = movei;
		curj = movej;
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			b[i][j] = board_copy[i][j];
		}
	}
	answer = min(answer, tmp);
}

void MakeTurn(vector<int> seq, vector<pair<int, int>> tmp, int turn) {

	if (turn == seq.size()) {
		FindShortest(tmp);
	}
	else {
		tmp.push_back(make_pair(v[seq[turn]][0].x, v[seq[turn]][0].y));
		tmp.push_back(make_pair(v[seq[turn]][1].x, v[seq[turn]][1].y));
		MakeTurn(seq, tmp, turn + 1);
		tmp.pop_back();
		tmp.pop_back();
		tmp.push_back(make_pair(v[seq[turn]][1].x, v[seq[turn]][1].y));
		tmp.push_back(make_pair(v[seq[turn]][0].x, v[seq[turn]][0].y));
		MakeTurn(seq, tmp, turn + 1);
		tmp.pop_back();
		tmp.pop_back();
	}
}

void MakeSeq() {

	do {
		vector<pair<int, int>> tmp;
		MakeTurn(chc, tmp, 0);
	} while (next_permutation(chc.begin(), chc.end()));
}

int solution(vector<vector<int>> board, int r, int c) {
	R = r;
	C = c;
	b = board;
	for (int i = 0; i<board.size(); i++) {
		for (int j = 0; j<board[i].size(); j++) {
			if (board[i][j] != 0) {
				if (v[board[i][j]].size() == 0) {
					chc.push_back(board[i][j]);
				}
				v[board[i][j]].push_back({ i, j });
			}
		}
	}

	vector<int> tmp;
	sort(chc.begin(), chc.end());
	MakeSeq();
	return answer;
}