[C++] 백준 1035번 조각 움직이기

조각들을 전부 인접하도록 만들기 위해서
조각을 최소 몇번 움직여야 하는지 찾는 문제입니다.

브루트 포스 방식을 사용했습니다.

1. 조각이 있을 수 있는 모든 경우를 탐색합니다. (인접하지 않는 경우도 포함)
2. 각 경우마다 DFS를 통해서 연결되어 있는지 확인합니다.
3. 연결이 되어 있는 경우 계산된 값을 비교해서 작으면 넣어줍니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#define MAX 987654321
using namespace std;

int len;
int result = MAX;
bool visit[7][7];
char map[7][7];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
vector<pair<int, int> > v;

int calc(int a, int b, int c, int d)
{
	return abs(a - c) + abs(b - d);
}

void check(int a, int b)
{
	for (int i = 0; i < 4; ++i) {
		int x = b + moveX[i];
		int y = a + moveY[i];

		if (map[y][x] != '*' || visit[y][x]) {
			continue;
		}
		visit[y][x] = true;

		check(y, x);
	}
}

bool connect() {
	int c = 0;

	memset(visit, 0, sizeof(visit));
	for (int i = 1; i <= 5; ++i) {
		for (int j = 1; j <= 5; ++j) {
			if (map[i][j] == '*' && !visit[i][j]) {
				visit[i][j] = 1;
				++c;
				check(i, j);
			}
		}
	}

	if (c == 1) {
		return true;
	}
	else {
		return false;
	}
}

void DFS(int c, int d)
{
	if (d >= result) {
		return;
	}

	if (c == len) {
		if (connect()) {
			result = min(result, d);
		}
		return;
	}

	for (int i = 1; i <= 5; ++i) {
		for (int j = 1; j <= 5; ++j) {
			if (map[i][j] == '.') {
				map[i][j] = '*';
				DFS(c + 1, d + calc(v[c].first, v[c].second, i, j));
				map[i][j] = '.';
			}
		}
	}
}

int main(int argc, char * argv[])
{
	string s;

	memset(map, ' ', sizeof(map));
	for (int i = 1; i <= 5; ++i) {
		for (int j = 1; j <= 5; ++j) {
			cin >> map[i][j];
			if (map[i][j] == '*') {
				v.push_back(make_pair(i, j));
				map[i][j] = '.';
			}
		}
	}

	len = v.size();
	DFS(0, 0);

	cout << result << endl;

	return 0;
}