[백준/BOJ] 백준 1035번 : 조각 움직이기

www.acmicpc.net/problem/1035

1035번: 조각 움직이기

조각의 개수만큼 보드에서 위치를 선택을 하는 모든 경우를 고려하고 그 선택들이 모두 연결되어 있다면 각 조각의 초기 위치에서 각각의 위치로 가는 모든 경우를 고려해서 이동 횟수를 구하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int star_num = 0;
vector<pair<int, int>> star;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int visited[5][5];
int result = 987654321;

void Pre_visited()
{
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			visited[i][j] = 0;
}

//연결된 개수를 구한다
int Connect_num(pair<int, int> here, vector<vector<int>>& shape_board)
{
	visited[here.first][here.second] = 1;
	int ret = 1;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < 5 && there.second >= 0 && there.second < 5 && visited[there.first][there.second] == 0 && shape_board[there.first][there.second] == 1)
		{
			ret += Connect_num(there, shape_board);
		}
	}

	return ret;
}

int Find_depth(int here_num, pair<int, int> start, vector<vector<int>>& check_board)
{
	vector<vector<int>> depth(5, vector<int>(5, 0));
	vector<vector<int>> discovered(5, vector<int>(5, 0));
	queue<pair<int, int>> q;

	depth[start.first][start.second] = 0;
	discovered[start.first][start.second] = 1;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//목적지에 도착했을때
		if (check_board[here.first][here.second] == here_num)
			return depth[here.first][here.second];

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);
			if (there.first >= 0 && there.first < 5 && there.second >= 0 && there.second < 5 && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}

		}
	}

	return 987654321;
}

void Solve(int select_start, vector<pair<int, int>>& select, vector<vector<int>>& shape_board)
{
	//별의 개수 만큼 위치를 골랐을때
	if (select.size() == star_num)
	{
		Pre_visited();

		//선택한 위치들이 모두 연결되었을때
		if (Connect_num(select[0], shape_board) == star_num)
		{
			vector<pair<int, int>> perm;

			for (int i = 0; i < select.size(); i++)
				perm.push_back(select[i]);

			sort(perm.begin(), perm.end());

			//각각 조각의 처음위치에서 연결된 요소로 가는 모든 경우를 고려한다
			do {

				int temp_result = 0;

				vector<vector<int>> check_board(5, vector<int>(5, -1));

				for (int i = 0; i < perm.size(); i++)
					check_board[perm[i].first][perm[i].second] = i;

				for (int i = 0; i < star.size(); i++)
					temp_result += Find_depth(i, star[i], check_board);

				result = min(result, temp_result);

			} while (next_permutation(perm.begin(), perm.end()));
		}

		return;
	}

	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
		{
			if (i * 5 + j < select_start)
				continue;

			//현재 위치를 선택
			shape_board[i][j] = 1;
			select.push_back(make_pair(i, j));

			Solve((i * 5) + j + 1, select, shape_board);

			//현재 위치 선택 해제
			select.pop_back();
			shape_board[i][j] = 0;
		}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	for (int i = 0; i < 5; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < input.size(); j++)
		{
			if (input[j] == '*')
			{
				star.push_back(make_pair(i, j));
				star_num++;
			}
		}
	}

	vector<vector<int>> shape_board(5, vector<int>(5, 0));
	vector<pair<int, int>> select;

	Solve(0, select, shape_board);

	cout << result;

	return 0;
}