191005 백준 알고리즘 문제풀기

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <tuple>
#include <queue>

using namespace std;

int map[8][8]; // 입력 맵
int check[8][8]; // 처음의 원본 check 저장용
int answer = 0;

int wallmap[8][8]; // 맵에 벽을 세웠을 때 저장용
int calcmap[8][8]; // 맵에 벽을 세웠을 때 연산용

vector<pair<int, int>> virus; // 바이러스 좌표 저장용

int dx[] = { -1,1,0,0 }; // 바이러스 입력 방향
int dy[] = { 0,0,-1,1 };

void init(int w, int h) // 벽 세웠을 때 저장용 맵을 원본 맵으로 초기화
{
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			wallmap[j][i] = check[j][i];
		}
	}
}

void calcinit(int w, int h) // 계산용 맵을 벽 세워진 맵으로 초기화
{
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			calcmap[j][i] = wallmap[j][i];
		}
	}
}

void spread(int w, int h) // 바이러스 퍼치기
{
	queue<pair<int, int>> q;

	calcinit(w, h); // 계산용 맵을 완성된 맵으로 초기화

	for (int j = 0; j < virus.size(); j++)
	{//모든 바이러스 좌표에 대해
		int x = virus[j].first;
		int y = virus[j].second;

		calcmap[y][x] = 2;
		q.push(make_pair(x, y));
		while (!q.empty())
		{
			int cx = q.front().first;
			int cy = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++)
			{
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (0 <= nx && nx < w && 0 <= ny && ny < h)
				{
					if (calcmap[ny][nx] == 0)
					{ // 계산용 맵에 바이러스가 퍼질 수 있는 다음 위치는 빈 공간(0)만 가능함
						calcmap[ny][nx] = 2; // 바이러스가 없다면 바이러스 퍼친다.
						q.push(make_pair(nx, ny));
					}
				}
			}
		}
	}


	int size = 0; // 바이러스 퍼치고 최댓값 저장
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			if (calcmap[j][i] == 0)
			{
				size++;
			}
		}
	}
	if (size > answer)
	{
		answer = size; // 최댓값을 결과로 초기화
	}
}


void wall(int w, int h, int cnt) // 벽 세우기
{
	if (cnt == 3)
	{
		spread(w, h); // 벽이 3개가 다 세워졌으면 바이러스 퍼치기
		return;
	}
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{ // 전체 좌표에 접근하며
			if (map[j][i] == 0 && wallmap[j][i] == 0)
			{ // 맵이 빈칸일 때만 벽을 세운다(바이러스 및 벽에는 벽 세울 수 없음)
				wallmap[j][i] = -1; // 벽 세우기
				wall(w, h, cnt + 1); // 벽 세우기(재귀)
				wallmap[j][i] = 0; // 앞의 재귀문을 빠져나오면 현재 위치를 다시 0으로 만들어야 한다.(함수의 재귀적 구성)
			}
		}
	}
}

int main()
{
	int h, w;
	scanf("%d %d", &h, &w);

	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 1)
			{
				check[j][i] = -1;
			}
			if (map[j][i] == 2)
			{
				virus.push_back(make_pair(i, j));
			}
		}
	}

	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			if (map[j][i] == 0)
			{ // 전체 좌표에서 첫 번째 벽을 세우는 과정
				init(w, h); // ccheck에 check 맵 복사(원본 맵 보관해야함)
				wallmap[j][i] = -1; //현재 위치에 벽 세우고
				wall(w, h, 1); // 벽 세우기 재귀함수 입장
				wallmap[j][i] = 0; // 현재 위치 벽 세운거 제거
			}
		}
	}

	printf("%d\n", answer);

	//system("pause");
	return 0;
}

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>
#include <algorithm>

using namespace std;

int nodes[20][20];
int answer = 2147483647; // int 최댓값 저장용

int calc(vector<int> team) // 팀 내의 능력치 합을 계산해 리턴한다.
{
	int len = team.size();
	vector<int> select(len); // 팀 인원 중 2명만 선택되는 선택수열을 생성
	select[len - 1] = 1;
	select[len - 2] = 1;
	int sum = 0; // 능력치 합 저장
	vector<int> temp; // 선택된 선수 인덱스 저장용

	do
	{
		temp.clear(); // 선택된 선수 인덱스 저장 스택 초기화

		for (int i = 0; i < len; i++)
		{
			if (select[i] == 1)
			{
				temp.push_back(i); // temp에 총 두명을 선택해 인덱스 저장
			}
		}
		sum += nodes[team[temp[0]]][team[temp[1]]]; // temp에는 해당 선수의 인덱스가 저장
		sum += nodes[team[temp[1]]][team[temp[0]]]; // 따라서 team의 인덱스로 들어가 서로 능력치 계산되어 더해져야 함
	} while (next_permutation(select.begin(), select.end())); // 다음 선택수열

	return sum; // 최종 합을 리턴
}

int main()
{
	int N;
	scanf("%d", &N);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &nodes[j][i]);
		}
	}
	
	vector<int> check(N); // 사람들 중 선수 고르기용 선택 수열 생성
	for (int i = 0; i < N / 2; i++)
	{
		check[N - 1 - i] = 1; // 맨 뒤부터 중간까지 1로 채워 선택한다.
	}
	
	int sa;
	int sb;2
	int sub;
	vector<int> idx_a; // a 팀 인덱스
	vector<int> idx_b; // b 팀 인덱스
	do 
	{
		idx_a.clear(); // 각 인덱스 초기화
		idx_b.clear();

		// 선택수열을 이용해 팀을 가름
		for (int i = 0; i < N; i++)
		{
			if (check[i] == 1)
			{
				idx_a.push_back(i);
			}
			else
			{
				idx_b.push_back(i);
			}
		}

		sa = calc(idx_a); // 각 갈라진 팀의 능력치 합을 리턴
		sb = calc(idx_b);
		sub = abs(sa - sb);
		if (sub < answer) // 최솟값을 정답으로 저장
		{
			answer = sub;
		}

	} while (next_permutation(check.begin(), check.end())); // 다음 선택순열

	printf("%d\n", answer);
	//system("pause");
	return 0;
}