191017 백준 알고리즘 문제풀기

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

#define MAX 2147483647

using namespace std;

struct camera
{
	int x, y, type;
};

int map[9][9]; // 맵 저장
int chosen_dir[9][9]; // 선택된 방향
int calc_map[9][9]; // 계산용 맵
vector<camera> cams;

int dx[] = { 0, 1,0,-1,0 }; // 1, 2, 3, 4 index는
int dy[] = { 0, 0,1,0,-1 }; // 우, 하, 좌, 상 순서

int num_cams = 0;
int answer = MAX;

void init_calcmap(int h, int w)
{ // 계산용 맵을 초기화한다.
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			calc_map[j][i] = chosen_dir[j][i];
		}
	}
}

void viewer(int h, int w, int nx, int ny, int dir)
{ // 해당 방향으로 끝날때까지 check한다.
	while (1)
	{
		nx += dx[dir];
		ny += dy[dir];
		if (nx < 0 || w <= nx || ny < 0 || h <= ny) break; // 범위 벗어나면 끝
		if (map[ny][nx] == 6) break; // 벽 나오면 끝
		calc_map[ny][nx] = 1;
	}
	return;
}

void view_map(int h, int w, int cx, int cy, int type, int dir)
{ // 카메라의 종류에 따라 맵을 완성시킨다.
	int nx = cx;
	int ny = cy;
	if (type == 1)
	{
		calc_map[cy][cx] = 1; // 현재위치 찍고
		viewer(h, w, nx, ny, dir); // 본다.
	}
	else if (type == 2)
	{// 2번 방향 좌우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 좌우 1, 3
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 2)
		{// 상하 4, 2
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 2);
		}
	}
	else if (type == 3)
	{// 3번 방향 상우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 상우 4, 1
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
		}
		if (dir == 2)
		{// 우하 1, 2
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);

		}
		if (dir == 3)
		{// 하좌 2, 3
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 4)
		{// 좌상 3, 4
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
		}
	}
	else if (type == 4)
	{// 4번 방향 좌상우
		calc_map[cy][cx] = 1; // 현재위치 찍고
		if (dir == 1)
		{// 좌상우 3, 4, 1
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
		}
		if (dir == 2)
		{// 상우하 4, 1, 2
			viewer(h, w, nx, ny, 4);
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);
		}
		if (dir == 3)
		{// 우하좌 1, 2, 3
			viewer(h, w, nx, ny, 1);
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
		}
		if (dir == 4)
		{// 하좌상 2, 3, 4
			viewer(h, w, nx, ny, 2);
			viewer(h, w, nx, ny, 3);
			viewer(h, w, nx, ny, 4);
		}
	}
	else //(type == 5)
	{
		calc_map[cy][cx] = 1; // 현재위치 찍고
		//4방향
		for (int i = 1; i < 5; i++)
		{
			viewer(h, w, nx, ny, i);
		}
	}
	return;
}

void calc(int h, int w)
{
	// 사각지대 만들기
	for (int i = 0; i < num_cams; i++)
	{//카메라들 동안
		int cx = cams[i].x;
		int cy = cams[i].y;
		int type = cams[i].type;
		int cd = chosen_dir[cy][cx];
		view_map(h, w, cx, cy, type, cd); // 현재 카메라가 보는 맵 만들기.
	}

	// 사각지대 세기
	int cnt = 0;
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			if (map[j][i] == 0)
			{//카메라 감시 가능한 구간만
				if (calc_map[j][i] == 0)
				{//사각지대 세기
					cnt++;
				}
			}
		}
	}
	//정답 비교
	if (cnt < answer) answer = cnt;
}

void dfs(int h, int w, int cnt)
{
	if (cnt == num_cams)
	{// 마지막 카메라까지 방향을 골랐으면
		init_calcmap(h, w); // 계산용 맵 초기화하고
		calc(h, w); // 계산을 시작한다.
		return;
	}
	//가능한 카메라 기본 방향은 4방향으로 하고
	int dir_cnt = 4;
	if (map[cams[cnt].y][cams[cnt].x] == 2) dir_cnt = 2; // 2번카메라는 2방향
	if (map[cams[cnt].y][cams[cnt].x] == 5) dir_cnt = 1; // 5번카메라는 1방향
	for (int i = 1; i <= dir_cnt; i++)
	{//모든 카메라 방향동안
		chosen_dir[cams[cnt].y][cams[cnt].x] = i;//현재 순번 카메라 좌표의 방향을 찍고
		dfs(h, w, cnt + 1); //다음 카메라로 넘어간다.
	}

}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < M; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] != 0 && map[j][i] != 6)
			{//카메라라면
				cams.push_back({ i,j,map[j][i] }); // 카메라들 저장
				//x, y, type, dir
			}
		}
	}
	//카메라 개수 세고
	num_cams = cams.size();
	//경우의 수 만들기 시작
	dfs(N, M, 0);

	//정답
	printf("%d\n", answer);

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

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

#define MAX 2147483647

using namespace std;

struct virus
{
	int x, y, activate; // 각각 좌표와 활성화 여부를 저장한다.
};

int map[51][51]; // 맵 저장용
int calc_map[51][51]; // 계산맵 저장용

int dx[] = { -1,1,0,0 }; // 이동방향
int dy[] = { 0,0,-1,1 };

vector<virus> viruses; // 바이러스 정보 저장
int num_virus = 0; // 활성화 바이러스 개수

int answer = MAX;

void spread(int N)
{// 바이러스 퍼치기
	//맵 초기화
	memset(&calc_map, 0, sizeof(calc_map)); // 계산맵을 초기화하고
	
	queue<pair<int, int>> q;
	
	for (int i = 0; i<int(viruses.size()); i++)
	{//전체 바이러스 중
		//활성화 바이러스 우선 활성화해서 큐에 넣는다.
		if (viruses[i].activate == 0) continue;
		calc_map[viruses[i].y][viruses[i].x] = 1;
		q.push(make_pair(viruses[i].x, viruses[i].y));
	}
	// 활성화바이러스들부터 먼저 탐색을 시작해야 전체적으로 매 초마다 고르게 퍼져간다.
	// 그렇지 않으면 첫 번째 바이러스가 끝날때까지 무조건 다 돌게되어 올바르지 않게 동작한다!
	
	while (!q.empty())
	{
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = cx + dx[k];
			int ny = cy + dy[k];
			if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue; // 범위 벗어나면 지나감
			if (map[ny][nx] == 1) continue; // 벽 만나면 지나감
			if (calc_map[ny][nx] != 0) continue; // 방문한적 있음 지나감
			if (map[ny][nx] == 2)
			{//만약 다음이 비활성화 바이러스라면
				int cnt = 0;
				for (int t = 0; t < 4; t++)
				{
					int tx = nx + dx[t];
					int ty = ny + dy[t];
					if (tx < 0 || N <= tx || ty < 0 || N <= ty) continue; // 범위 벗어나면 지나감
					if (map[ty][tx] == 1) continue; // 벽 만나면 지나감
					if (calc_map[ty][tx] != 0) continue; // 방문한적 있음 지나감
					//갈 데가 있으면 count
					cnt++;
				}
				if (cnt == 0)
				{//갈 곳이 한군데도 없다면 check만 한다.
				// check만 하는게 비활성화를 활성화 상태로 만드는것이다.
				// 어차피 비활성화 상태 바이러스도 바이러스이므로 다음에 퍼지지 않는다면
				// 시간이 소요되면 안되므로 예외처리한다.
					calc_map[ny][nx] = calc_map[cy][cx];
				}
				else
				{//갈 곳이 있으면 다음 부분으로 퍼치기 위해 시간이 소요되며 퍼진다.
					calc_map[ny][nx] = calc_map[cy][cx] + 1;
					q.push(make_pair(nx, ny));
				}
			}
			else
			{//만약 다음이 비활성화 바이러스가 아니라면 그냥 퍼진다.
				calc_map[ny][nx] = calc_map[cy][cx] + 1;
				q.push(make_pair(nx, ny));
			}
				
		}
	}

	// 바이러스 최대 시간 찾기
	int maxval = -1;
	bool iszero = false;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			if (map[j][i] == 1) continue;//벽은 넘어가고
			if (calc_map[j][i] == 0)
			{// 0이 있다면 계산하나 마나니까 빠져나감
				iszero = true;
				break;
			}
			if (maxval < calc_map[j][i])
			{//맵에서 최댓값 찾고
				maxval = calc_map[j][i];
			}
		}
	}
	if (iszero == false && maxval < answer)
	{
		answer = maxval;
	}
}

void dfs(int N, int idx, int cnt)
{ // index 번째 바이러스부터 시작해서 활성화 바이러스를 다 고른다음 퍼친다.
	if (cnt == num_virus)
	{//활성화 바이러스를 다 골랐으므로
		spread(N); // 퍼친다.
		return;
	}
	// 인덱스는 idx번째부터 시작한다.
	// 그래야 중복선택되는것을 막을 수 있다.
	// 즉, 해당 idx번째가 골라졌을때 계산 가능한 경우의 수는 모두 구해졌기에
	// 다음부터 볼 필요 없으므로 idx로 초기화한다.
	for (int i = idx; i < int(viruses.size()); i++)
	{//전체 바이러스들에 대해
		if (viruses[i].activate == 0)
		{// 활성화 되지 않았다면
			viruses[i].activate = 1; // 해당 바이러스 활성화 시키고
			dfs(N, i + 1,cnt + 1); // 여기가 핵심!!
			// 현재 인덱스 다음 바이러스부터 고려하면 된다.
			viruses[i].activate = 0; // 다시 비활성화 한다.
		}
	}
}

int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	int wall_cnt = 0;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 2) viruses.push_back({ i,j,0 });
			if (map[j][i] == 1) wall_cnt++;
		}
	}
	num_virus = M;

	if ((wall_cnt + int(viruses.size())) == (N*N))
	{// 전체 맵에 비활성화 바이러스로 다 찬 경우, 이미 바이러스가 다 찬 상태이므로 0초 소요되는게 맞다.
		printf("%d\n", 0);
	}
	else
	{// 아닌 경우라면 연산을 수행
		//바이러스 선택하기
		dfs(N, 0, 0);

		if (answer == MAX) answer = -1;
		else answer -= 1;
		printf("%d\n", answer);
	}

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

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>

#define MAX 2147483647

using namespace std;

struct info
{
	int x, y, chosen;
};

int map[51][51];

vector<info> chicken;
vector<info> houses;

int answer = MAX;

void calc_distance(int N)
{
	int distances = 0;

	for (int i = 0; i<int(houses.size()); i++)
	{
		int min_dist = MAX;
		for (int k = 0; k<int(chicken.size()); k++)
		{// 치킨집까지의 거리중 최솟값을 저장
			if (chicken[k].chosen != 1) continue;
			int dist = abs(houses[i].x - chicken[k].x) + abs(houses[i].y - chicken[k].y);
			if (dist < min_dist) min_dist = dist;
		}
		distances += min_dist;
	}
	if (distances < answer) answer = distances; // 최솟값 저장
}

void dfs(int idx, int cnt, int num_chicken, int N)
{
	if (cnt == num_chicken)
	{
		calc_distance(N);
		return;
	}

	for (int i = idx; i<int(chicken.size()); i++)
	{//전체 치킨집동안
		if (chicken[i].chosen == 1) continue; // 골라졌으면 넘어간다.
		chicken[i].chosen = 1; // 고르고
		dfs(i + 1, cnt + 1, num_chicken, N); // 다음 인덱스로 넘겨 들어간다.(중복 방지)
		chicken[i].chosen = 0; // 고르기 해제
	}
}


int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	//입력받기
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 2) chicken.push_back({ i,j,0 });
			if (map[j][i] == 1)	houses.push_back({ i,j,-1 });
		}
	}

	for (int idx = 1; idx <= M; idx++)
	{// idx = 골라지는 치킨집 갯수
		dfs(0, 0, idx, N);
	}

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

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