boj,백준 ) 17142. 연구소 3 (C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

2. 문제 개요

n*n의 맵에서 여러 개의 바이러스중 m개만 활성화시킬 때, 가장 빨리 모든 맵을 바이러스로 채우는 시간을 구하기.

 

3. 문제 힌트!!

 바이러스를 m개 선택하기 -> 조합, DFS

 선택한 바이러스를 퍼트리기 -> BFS

 끝나는 조건 -> 마지막 탐색하지 않은 1칸이 비활성화된 바이러스라면?...

 

4. 문제 풀이

맵을 입력받고, 있는 바이러스들을 모두 2에서 3으로 변경시켜주었다 ( 자기 편한 대로 하면 됨. 안 해도 되는 부분.)

그리고 바이러스들의 정보, 즉 좌표와 최단거리변수를 담을 벡터를 만들고 저장해둔다.

 

dfs로 조합 시작.

Brute force방식이다. dfs로 바이러스들을 선택했을 때 활성화된 바이러스들을 3에서 2로 바꿔준다.

그 바이러스들을 가지고 BFS를 시작한다.

하지만 3을만날때 맵에 0이 없는지 check 해야 한다. 예를 들면

[3 0 1 0]

[0 0 1 0]

[0 0 2 0]

[1 1 0 0]

가 있다고 가정하면, 3번째 시간에

[3 2 1 2]

[2 2 1 2]

[2 2 2 2]

[1 1 2 2]

가 된다. 문제대로라면 끝나야 한다. 하지만 특별한 처리를 안 해주면 3도 방문하고 오답인 4를 얻게 될 것이다.

 

문제의 코드에서는 queue에서 pop 할 때 최솟값을 갱신하고 있으므로,

3을 만났을 때 0이 없다면 continue를 해주어 queue의 모든 원소들이 빠져나 올 수 있도록 했다.

 

그리고 bfs를 마치고 나서 맵에 0이 존재하면 바이러스를 채울 수 없는 상태이므로 바로 return 해주었다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct VIRUS
{
	int y, x;
	int time;
};

int n, m; //m개의 바이러스 선택
int map[50][50];
vector<VIRUS> v;
int minval = 0x7f7f7f7f;
int selected[10];

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

void cp_map(int src[][50], int dest[][50])
{
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			src[i][j] = dest[i][j];
	return;
}

void dfs(int depth, int start)
{
	if (depth == m)
	{
		//bfs
		int clone[50][50];
		cp_map(clone, map);

		queue<VIRUS> q;
		bool visited[50][50] = { false, };

		//activate virus
		for (int i = 0; i < m; ++i)
		{
			int s = selected[i];
			clone[v[s].y][v[s].x] = 2;

			VIRUS start;
			start.y = v[s].y;
			start.x = v[s].x;
			start.time = v[s].time;

			q.push(start);
			visited[v[s].y][v[s].x] = true;
		}
		int mintime = 0;
		while (!q.empty())
		{
			VIRUS cur = q.front(); q.pop();
			
			if (cur.time > mintime)
				mintime = cur.time;

			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				int ntime = cur.time + 1;

				if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[ny][nx] || clone[ny][nx] == 1)
					continue;

				if (clone[ny][nx] == 3)
				{
					bool check = true;
					for (int i = 0; i < n; ++i)
						for (int j = 0; j < n; ++j)
							if (clone[i][j] == 0)	check = false;

					if (check)
						continue;
				}

				clone[ny][nx] = 2;
				visited[ny][nx] = true;
				VIRUS next;
				next.x = nx, next.y = ny;
				next.time = ntime;
				q.push(next);
			}
		}
        
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (clone[i][j] == 0)	return;

			minval = min(minval, mintime);
		return;
	}
	
	for (int i = start; i < v.size(); ++i)
	{
		selected[depth] = i;
		dfs(depth + 1, i + 1);
	}
	return;
}
int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2)
			{
				map[i][j] = 3;
				VIRUS temp;
				temp.y = i, temp.x = j;
				temp.time = 0;
				v.push_back(temp);
			}
		}

	//combination
	dfs(0, 0);

	if (minval == 0x7f7f7f7f)
		printf("-1");
	else
		printf("%d", minval);

	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~