<SWEA> #1767 DFS, Brute Force 프로세서 연결하기 c++

문제, 참고

Idea

• cell의 정보를 입력받을 때, core가 있는 좌표를 따로 저장한다
• 이때 벽에 붙어 있는 core는 이미 전원에 연결이 되어 있으므로 저장하지 않는다
• 한 core에 전선을 연결하지 않거나, 동서남북 방향으로 전선을 연결해보았을 경우를 모두 따져보는 DFS, Brute force 방법을 사용

Input

• 문제에서 최대한 많은 core에 전원을 연결했을 경우, 전선 길이 합의 최소를 구하는 문제이므로 core의 최대 개수(=ans2)와 전선 길이 합의 최소(=ans1)를 모두 체크하여야 함
• cell의 정보를 입력받을 때, core의 좌표를 입력받음

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		cin >> map[i][j];
		if (map[i][j] == CELL) {
			if (i == 0 || j == 0 || i == N - 1 || j == N - 1) continue;
			core.push_back(make_pair(i, j));
		}
	}
}
coreSize = core.size();

DFS

• 현재 몇 번째 core를 탐색하는지 (int C), 이때까지 추가된 core는 몇 개 인지 (int core_cnt), 이때까지 추가된 전선의 길이는 얼마인지 (int power_cnt)를 파라미터로 둔다
• 기저 조건은 마지막 core까지 탐색했을 때이고, 현재까지 추가된 코어가 이전에 있던 코어수보다 많다면 최대코어수와 전선의 최소 길이를 갱신해줌
• 그렇지 않고 추가된 최대 코어수와 현재까지 추가된 코어 수와 같다면 전선의 길이를 비교해서 최솟값을 갱신해줌

	if (C == coreSize) {
		if (core_cnt > ans2) {
			ans2 = core_cnt;
			ans1 = power_cnt;
		}
		else if (core_cnt == ans2) {
			if (ans1 > power_cnt)
				ans1 = power_cnt;
		}
		return;
	}

• 현재 탐색하려는 코어의 좌표에서 상하좌우로 움직여본다
• 한 칸 씩 움직였을 때 다른 코어나 전선과 충돌하지 않고 벽에 도착했을 때, 전선을 map에 추가해줌
• dfs 호출하여 다음 코어를 탐색하고, 다시 돌아왔을 때 map에서 전선을 지워줌

	if (flag) {
		for (int j = 0; j < coord.size(); j++) 
			map[coord[j].y][coord[j].x] = POWER;

		dfs(C + 1, core_cnt + 1, power_cnt + coord.size());

		for (int j = 0; j < coord.size(); j++)
			map[coord[j].y][coord[j].x] = EMPTY;
	}

• 코어에 동서남북 방향으로 아무 전선을 추가하지 않은 경우에도 다음 dfs 함수 호출

Source Code

#include <iostream>
#include <vector>
#include <string.h>

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

const int MAX = 13;

enum {EMPTY, CELL, POWER};

using namespace std;

struct COORD {
	int y, x;
};


int coreSize;
int T, N;

int map[MAX][MAX];
int ans1=MAX*MAX; // 전선 최소 개수
int ans2=0; // 최대 설치 cell
vector<pair<int, int> >core;


void dfs(int C, int core_cnt, int power_cnt) {

	if (C == coreSize) {
		if (core_cnt > ans2) {
			ans2 = core_cnt;
			ans1 = power_cnt;
		}
		else if (core_cnt == ans2) {
			if (ans1 > power_cnt)
				ans1 = power_cnt;
		}
		return;
	}

	for (int i = 0; i < 4; i++) {
		vector<COORD> coord;
		bool flag = false;

		int ny = core[C].first;
		int nx = core[C].second;

		while (1) {
			if (ny == 0 || nx == 0 || ny == N - 1 || nx == N - 1) {
				flag = true;
				break;
			}

			ny += dy[i];
			nx += dx[i];

			if (map[ny][nx] == EMPTY)
				coord.push_back({ ny,nx });
			else
				break;
		}
		if (flag) {
			for (int j = 0; j < coord.size(); j++) 
				map[coord[j].y][coord[j].x] = POWER;

			dfs(C + 1, core_cnt + 1, power_cnt + coord.size());

			for (int j = 0; j < coord.size(); j++)
				map[coord[j].y][coord[j].x] = EMPTY;
		}
	}

	dfs(C + 1, core_cnt, power_cnt);
}

void solution() {
	cin >> T;
	for (int i = 1; i <= T; i++) {
		cin >> N;

		memset(map, 0, sizeof(map));
		ans1 = MAX * MAX;
		ans2 = 0;
		core.clear();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
				if (map[i][j] == CELL) {
					if (i == 0 || j == 0 || i == N - 1 || j == N - 1) continue;
					core.push_back(make_pair(i, j));
				}
			}
		}
		coreSize = core.size();

		dfs(0,0,0);

		cout << "#" << i << " " <<ans1<<endl;
	}
}

int main(int argc, char** argv) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}

map을 이차원 벡터로 선언해서 함수로 넘기는 걸 계속 하다가 시간 초과가 났다..