[SWEA / 삼성A형기출] 1767 프로세서 연결하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

SW Expert Academy

1767 프로세서 연결하기 

알고리즘 : 비트마스크 DFS

완전 탐색 방식으로 해결할 수 있는 문제이며 전선을 나타내는데 한 줄(N)이 12인 점을 생각해보니

비트 마스크 기법을 사용하면 2차원 배열이 아닌 1차원 배열로 맵을 관리할 수 있고, 재귀에서도 시간을 

더욱 적게 사용할 거 같아 이를 이용해 문제를 풀이하였습니다.

 

기본 풀이 원리

 

 

< CODE >

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

#define MAX 20

vector<pair<int, int>> v;

int mSize;
int result = INT_MAX;
int rConnect = 0;

// testCase 마다 초기화 
inline void init()
{
	result = INT_MAX;
	rConnect = 0;
	v.clear();
}

// 해당 줄의 bit 위치에 core나 전선이 있는지 확인
inline bool bitCheck(int bit, int chk)
{
	return bit & (1 << chk);
}

// 해당 줄의 일정 영역의 확인
inline bool bitCheckSome(int bit, int chk, bool bef)
{
	int b = ((1 << chk) - 1);

	if (bef)
		return bit & b;
	else
		return bit & ((1 << mSize) - (b << 1) - 2);
}

// 비트 추가
inline void bitAdd(int & bit, int add)
{
	bit = bit | (1 << add);
}

// 비트 다중 추가
inline void bitAddSome(int & bit, int add, bool bef)
{
	int b = ((1 << add) - 1);

	if (bef)
		bit = bit | ((b << 1) + 1);
	else
		bit = bit | ((1 << mSize) - b - 1);
}

void dfs(int cnt, int total, int connect, int map[MAX])
{
	if (cnt == v.size())
	{
		if (rConnect < connect)
		{
			rConnect = connect;
			result = total;
		}
		else if (rConnect == connect && result > total)
			result = total;

		return;
	}

	if (v.size() - cnt + connect < rConnect)
		return;

	int tMap[MAX];

	// 이전 재귀 탐색이후 맵 복원을 위한 tempMap 생성
	for (register int i = 0; i < mSize; i++)
		tMap[i] = map[i];

	int y = v[cnt].first;
	int x = v[cnt].second;

	// 이전 재귀가 이 코어의 위를 지나고 있다면 잘못 된 재귀이므로 백트래킹
	if (bitCheck(map[y], x)) 
		return;

	// 가장자리의 코어 우선 처리
	if (y == 0 || y == mSize - 1 || x == 0 || x == mSize - 1)
	{
		bitAdd(map[y], x);

		dfs(cnt + 1, total, connect + 1, map);

		map[y] = tMap[y];
	}
	else
	{
		// 현재 상황에서 상하좌우 방향으로 가능한지 확인
		bool dir[4] = { 0, };
		
		dir[0] = bitCheckSome(map[y], x, true);
		dir[1] = bitCheckSome(map[y], x, false);

		for (register int i = 0; i < y; i++)
		{
			dir[2] = bitCheck(map[i], x);

			if (dir[2])
				break;
		}

		for (register int i = y + 1; i < mSize; i++)
		{
			dir[3] = bitCheck(map[i], x);

			if (dir[3])
				break;
		}

		if (!dir[0])
		{
			bitAddSome(map[y], x, true);

			dfs(cnt + 1, total + x, connect + 1, map);

			map[y] = tMap[y]; // 비트마스크를 사용하여  O(n)이 걸릴 복원이 O(1)만에 이루어짐
		}
		if (!dir[1])
		{
			bitAddSome(map[y], x, false);

			dfs(cnt + 1, total + (mSize - x - 1), connect + 1, map);

			map[y] = tMap[y];
		}
		if (!dir[2])
		{
			for (register int i = 0; i <= y; i++)
				bitAdd(map[i], x);

			dfs(cnt + 1, total + y, connect + 1, map);

			for (register int i = 0; i <= y; i++)
				map[i] = tMap[i];
		}
		if (!dir[3])
		{
			for (register int i = y; i < mSize; i++)
				bitAdd(map[i], x);

			dfs(cnt + 1, total + (mSize - y - 1), connect + 1, map);

			for (register int i = y; i < mSize; i++)
				map[i] = tMap[i];
		}

		// 이 코어를 연결 하지 않는 경우
		bitAdd(map[y], x);
		dfs(cnt + 1, total, connect, map);
		map[y] = tMap[y];
	}
}

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

	int tests;

	cin >> tests;

	while (tests--)
	{
		static int t = 1;

		init();

		cin >> mSize;

		for (register int i = 0; i < mSize; i++)
		{
			for (register int j = 0; j < mSize; j++)
			{
				int num;

				cin >> num;

				if (num == 1)
					v.push_back(make_pair(i, j));
			}
		}

		int m[MAX] = { 0, };

		dfs(0, 0, 0, m);

		cout << "#" << t++ << ' ';
		cout << result << '\n';
	}

	return 0;
}

 

 

최초 242ms가 나왔고, 백트래킹과 최적화 작업을 해주어 13ms까지 줄였습니다.

 

#삼성 A형 #프로세서연결하기 풀이 #1767 #SWEA