백준 알고리즘 17142_연구소 3 C

문제

(링크)17142번: 연구소 3 (acmicpc.net)

17142번: 연구소 3

사고과정

먼저 4방향으로 퍼지고, 퍼지는데 걸리는 총 시간을 구하는 것이므로 bfs(queue)를 이용해야한다. 그리고 바이러스중 활성바이러스로 만들 것을 고르는 것은 N중 반복문이나 재귀함수를 사용하면 되는데 고르는 수가 변수이므로 재귀함수를 이용하면 편할 것이다. 그리고 각 경우 중 가장 짧은 소요시간을 구하는데, 어떤 경우에도 모든 칸을 확산시키지 못하면 -1을 출력해야 하므로 각 경우마다 전체 맵을 탐색해야 한다.

 

내코드

#include <stdio.h>
#include <stdlib.h>

int size, vir_num,virus_pick,spread_flag=0;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

typedef struct {
	int x, y, time;
}Point;

int pick[10];

void clear(int** visit) {
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			visit[i][j] = 0;
		}
	}
}
int isSpread(int** map, int** visit) {
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			if ((map[i][j] == 0) && visit[i][j] == 0) {//빈 공간,혹은 선택하지 않은 바이러스 중 바이러스가 안퍼진 곳이 있으면
				return 0;
			}
		}
	}
	return 1;
}
void pickVir(int start, int count, Point* v, int* answer,int**map,int** visit) {
	pick[count - 1] = start;//count는 1부터 시작
	if (count == virus_pick) {
		Point queue[2500];
		int front = 0, rear = 0;
		int temp_ans=0;
		for (int i = 0; i < virus_pick;i++) {
			int r = pick[i];
			queue[rear].x = v[r].x;
			queue[rear].y = v[r].y;
			queue[rear].time = v[r].time;
			visit[v[r].y][v[r].x] = 1;
			rear++;
		}

		while (front < rear) {
			int popX = queue[front].x;
			int popY = queue[front].y;
			int popT = queue[front].time;
			if (temp_ans < popT && map[popY][popX]!=2)temp_ans = popT;//각 경우의 수에서 걸린 시간을 저장
			front++;

			for (int i = 0; i < 4; i++) {
				int X = popX + dx[i];
				int Y = popY + dy[i];

				if (X >= 0 && X < size && Y >= 0 && Y < size) {
					if ((map[Y][X] == 0||map[Y][X]==2) && visit[Y][X] == 0) {
						queue[rear].x = X;
						queue[rear].y = Y;
						queue[rear].time = popT + 1;
						visit[Y][X] = 1;
						rear++;
					}
				}
			}

		}
		if (isSpread(map, visit)) {
			if (*answer > temp_ans)*answer = temp_ans;
			spread_flag = 1;
		}
		clear(visit);
		return;
	}

	for (int i = start + 1; i < vir_num; i++) {
		pickVir(i, count + 1, v, answer,map,visit);
	}
}



int main() {
	int i, j;
	scanf_s("%d %d", &size, &virus_pick);
	int** map = (int**)malloc(size * sizeof(int*));
	int** visit = (int**)calloc(size, sizeof(int*));
	for (i = 0; i < size; i++) {
		map[i] = (int*)malloc(size * sizeof(int));
		visit[i] = (int*)calloc(size, sizeof(int));
	}
	Point* virus = (Point*)malloc(10 * sizeof(Point));//virus의 위치 저장할 곳 및 나중에 여기서 선택할 것임
	vir_num = 0;
	for (i = 0; i < size; i++) {
		for (j = 0; j < size; j++) {
			scanf_s("%d", &map[i][j]);
			if (map[i][j] == 2) {
				virus[vir_num].x = j;
				virus[vir_num].y = i;
				virus[vir_num].time = 0;
				vir_num++;
			}
		}
	}

	int answer = 100000;
	for (i = 0; i <= vir_num - virus_pick; i++) {
		pickVir(i, 1, virus, &answer,map,visit);
	}
	if (!spread_flag)answer = -1;

	printf("%d", answer);


	for (i = 0; i < size; i++) {
		free(map[i]);
		free(visit[i]);
	}
	free(map);
	free(visit);
	free(virus);
	return 0;
}

먼저 virus Point배열에 입력으로 주어진 비활성 바이러스들의 좌표를 저장한다. 이후 바이러스를 고르는 함수에서 사용할 것이다. 이후 pickVir함수에서 입력으로 주어진 활성산소 개수만큼 바이러스를 고른다. 이 때, pick배열에 순서대로 고른 바이러스의 index를 저장하고, 선택한 바이러스가 겹치는 것을 방지하기 위해 해당 바이러스의 이름을 인자로 전달한다. 이후 모든 바이러스를 골랐다면, bfs탐색을 하여 빈 공간을 채워간다. 여기서 중요한 것은 temp_ans를 사용하여 해당 경우에서의 소요시간을 저장하는 것이다. 주의해야 할 점은, 비활성 바이러스가 활성 바이러스를 만나면 활성바이러스가 되어 queue에 추가된다는 것다. 또한 문제에서 구하는 것은 <빈칸이 바이러스로 가득 차는 시간>이므로, 마지막에 탐색되는 지점이 비활성 바이러스, 즉 queue의 마지막에 들어있는 것이 비활성바이러스인 경우를 예외로 둬야한다. 그래서 비활성바이러스가 들어있던 지점은 temp_ans에 갱신하지 않는다.

이후 isSpread함수를 이용하여 map의 빈칸 중 방문하지 않은 곳이 있다면 0을 return하고, 모두 탐색했다면 1을 return한 뒤 answer와 전역변수 spread_flag를 갱신한다. spread_flag는 <모든 경우에서, 바이러스 전파가 불가능한 경우>를 고려해야하기 때문에 설정한 것이다. 이후 visit을 clear하며 모든 경우를 탐색한다.

   

피드백

생각보다 조금 까다로운 문제였다. 문제에서 요구하는 조건이 은근 많았고 <비활성 바이러스가 활성 바이러스를 만나면 활성이 된다>라는 부분을 지나가듯 읽어서 코드를 짤 때 다시한번 문제를 읽게 되었다. 나중에 문제를 풀 땐, 조건이 많다면, 중요 조건을 메모하면서 문제를 풀 것