[C++] 백준 17142번 연구소 3

17142번: 연구소 3

 

삼성 SW 역량 테스트 기출 문제 

에 수록된 문제.

골드 4 문제이며 연구소 문제의 후속작(?)인 것 같다. 연구소 문제는 골드 5에 정답률도 55%를 기록하고 있지만,

이 문제는 골드 4에 정답률이 25%를 기록하고 있다.

연구소 문제는 그래프 탐색 이론 문제이고, 너비 우선 탐색(BFS)을 통해서 푸는 문제이다.

사실 왜 맞았는지 잘 모르겠다.

TC들이 제대로 나오지 않길래, 조건을 조금 수정해서 TC들이 잘 나와서 제출했더니 맞았습니다!!

가 나와버렸다...

한번 글을 쓰면서 정리해봐야겠다. (이왜맞?)

 

문제풀이

문제의 조건을 정리하면 다음과 같은 순서로 풀면 된다.

1. 크기 N과 바이러스가 처음에 활동하는 개수 M을 입력받고, 0(빈 칸), 1(벽), 2(바이러스가 있는 위치)를 입력받는다.
2. 바이러스 M개를 바이러스가 있는 위치들 중 할당하고, 바이러스를 퍼뜨리면 된다.
3. 바이러스는 상, 하, 좌, 우로 퍼질 수 있다. 이 때, 퍼지는데는 1초의 시간이 소요된다. 벽에는 퍼질 수 없다.
4. 바이러스가 활성화되지 않은 다른 바이러스를 만날경우 해당 바이러스가 활성화된다.

빈 칸들을 모두 바이러스로 채우는 최소 시간을 구하면 된다.

 

(4) 조건이 처음에 헷갈렸다. 바이러스가 다른 활성화되지 않은 바이러스를 만날경우 해당 바이러스를 활성화 시키면

1. 바로 상, 하, 좌, 우로 퍼져야 하는건지 / 2. 해당 칸에 도착한 이후 퍼져야 하는건지

문제에서 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 라는 조건이 있었다. 따라서 (4) 조건은 2와 같이 해당 칸에 도착한 이후 퍼져야 하는게 맞다.

 

또한, 우리는 빈 칸들만 채우면 된다. 즉, 비활성화 바이러스를 활성화 시키는 것은 빈 칸을 채우는 것이 아니므로 시간이 지난 것에 영향을 주어선 안된다.

예제 입력 7을 보면

5 1 2 2 2 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 2 2 1 1

위처럼 나와있다. 이미 빈 칸이 0개이므로, 0초 후에 모든 빈 칸을 바이러스로 채울 수 있게 된다.

즉, 바이러스 한 개를 할당하고, 다른 바이러스를 활성화 시키는 일은 시간이 지나는 것에 영향을 주어선 안된다는 뜻이다.

 

위 조건들을 가지고 코드로 구현하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

int widthHeight, virusCnt;
int totalEmptySpace;
int board[51][51];
bool visit[51][51];
vector<pair<int, int>> canPutVirusPointVec;
vector<pair<int, int>> currentVirusPointVec;
pair<int, int> direction[4] = {
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1}
};
int ans = 100000000;

사용한 STL과 변수

• widthHeight, virusCnt : 입력받는 N과 M
• totalEmptySpace : 처음에 격자의 정보를 입력받을 때, 0(빈 칸)의 개수를 저장해놓는 변수
• board 배열 : 격자의 정보를 저장해두는 배열
• visit 배열 : bfs를 진행할 때, 해당 칸을 방문했는지 기록하는 배열
• canPutVirusPointVec : 바이러스를 놓을 수 있는, 2(바이러스 칸)의 좌표를 저장해놓는 벡터
• currentVirusPointVec : 현재 할당한 M개의 바이러스들의 좌표를 담아두는 벡터
• direction 배열 : 상, 하, 좌, 우를 탐색할 때 좌표에 더해주기만 하면 되게 만들어놓은 배열
• ans : 결과값, 1억으로 초기화해두고 찾지못해서 그대로 1억이라면 -1을 출력하고 아니라면 ans를 출력한다.

 

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

	cin >> widthHeight >> virusCnt;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) { totalEmptySpace++; }
			else if (board[i][j] == 1) {
				board[i][j] = '-';
			}
			else if (board[i][j] == 2) { 
				board[i][j] = '*';
				canPutVirusPointVec.push_back({ i, j }); 
			}
		}
	}

	go(1, 0);

	if (ans != 100000000) {
		cout << ans;
	}
	else {
		cout << "-1";
	}

	return 0;
}

메인함수

 

처음에 N, M을 입력받은 후에, 격자의 정보를 입력받는다.

만일 격자의 칸이 0이라면 빈 칸이므로 totalEmptySpace변수에 1을 더해준다.

격자의 칸이 1이라면 벽이다. 사실 벽은 그대로 1로 두어도 상관은 없는데, 알아보기 쉽게 하기 위해 '-'로 바꿔준다.

격자의 칸이 2라면 바이러스를 둘 수 있는 칸이다. 해당 칸을 '*'로 바꾸어준 후에, canPutVirustPointVec에 해당 격자의 좌표를 입력해 놓는다.

 

모든 입력이 끝나면,

바이러스 M개를 할당하고 바이러스를 퍼뜨리는 메서드 go()를 호출한다.

첫번째 매개변수인 1은 첫번째 바이러스를 할당한다는 뜻이고, 뒤에 나오는 0은 canPutVirusPointVec의 0번째 idx부터 탐색한다는 뜻이다.

뒤에 더 자세히 설명하겠다.

 

그리고 할당하고 퍼뜨리는 작업이 끝나면 ans 값에 따라 -1, 또는 ans를 출력한다.

 

void go(int idx, int startVecIdx) {
	if (idx > virusCnt) {
		int ret = spreadVirus();
		if (ret != -1) {
			ans = min(ans, ret);
		}
	}
	else {
		for (int i = startVecIdx; i < canPutVirusPointVec.size(); i++) {
			int r = canPutVirusPointVec[i].first;
			int c = canPutVirusPointVec[i].second;
			currentVirusPointVec.push_back({ r, c });
			go(idx + 1, i + 1);
			currentVirusPointVec.pop_back();
		}
	}
}

바이러스 M개를 할당하는 메서드.

 

canPutVirusPointVec에 담겨있는 바이러스를 놓을 수 있는 좌표들 중 M개를 선택한다.

그리고 현재 idx번째를 뽑을 차례인데, 이게 virusCnt보다 크다면 (ex. 3개를 뽑아야 하는데 idx가 4라면)

바이러스를 모두 할당했다는 뜻이므로 바이러스를 퍼뜨린다.

바이러스를 퍼뜨리는 메서드 spreadVirus()는 int형 정수를 반환하는데, 이 때 모든 빈 칸에 바이러스를 퍼뜨리지 못했다면 -1을 반환한다.

반환된 값이 -1이 아니라면 현재 저장중인 ans와 비교해서 더 작은 값을 ans에 저장한다.

 

idx가 virusCnt보다 작다면 canPutVirusPointVec에 담겨있는 좌표들 중에서 하나를 고른다.

중복을 제거하기 위해 다음 go() 메서드의 두 번째 매개변수에는 현재 고른 i + 1을 다음 for 반복문의 시작idx로 넘겨준다.

 

int spreadVirus() {
	memset(visit, false, sizeof(visit));
	int tmpBoard[51][51];
	int tmpEmpty = totalEmptySpace;
	int retTime = 0;
	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			tmpBoard[i][j] = board[i][j];
		}
	}
	queue< pair<int, pair<int, int> > > q;
	
	for (pair<int, int> point : currentVirusPointVec) {
		int time = 0;
		int r = point.first;
		int c = point.second;
		tmpBoard[r][c] = time;
		q.push({ time, {r,c} });
		visit[r][c] = true;
	}

	while (!q.empty()) {
		int curTime = q.front().first;
		int curR = q.front().second.first;
		int curC = q.front().second.second;
		q.pop();

		for (pair<int, int> direc : direction) {
			int nxtTime = curTime + 1;
			int nxtR = curR + direc.first;
			int nxtC = curC + direc.second;
			if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight ||
				visit[nxtR][nxtC] == true || tmpBoard[nxtR][nxtC] == '-') {
				continue;
			}

			visit[nxtR][nxtC] = true;
			if (tmpBoard[nxtR][nxtC] == '*') {
				q.push({ nxtTime, {nxtR, nxtC} });
			}
			else {
				tmpEmpty--;
				q.push({ nxtTime, {nxtR, nxtC} });
			}
		}

		if (tmpBoard[curR][curC] != '*') {
			retTime = max(retTime, curTime);
		}
		tmpBoard[curR][curC] = curTime;
	}

	if (tmpEmpty == 0) {
		return retTime;
	}
	else {
		return -1;
	}
}

바이러스를 퍼뜨리는 메서드.

 

이 문제가 그래프 탐색 이론, BFS 문제인 이유는 이 부분 때문이다.

이 메서드는 다음과 같은 순서로 이루어져 있다.

 

1. visit 배열 초기화

2. 다음 변수들 생성.

• tmpBoard : Board 배열을 그대로 가져와서 사용하기 위한 배열.
• tmpEmpty : totalEmptySpace 변수를 가져와서 사용한다. 모든 BFS를 돌았을 때 이 값이 0이 아니라면 모든 빈 칸에 바이러스를 퍼뜨리지 못했다는 뜻이다.
• retTime : 몇 초가 지났는지 반환하는 값

3. tmpBoard 배열에 board 배열의 값 전달.

4. BFS용 큐 q 생성 : 처음 int는 해당 칸에 도달하는데 걸린 시간, 두번째 pair는 좌표

5. 현재 활성화시킨 바이러스 M개의 좌표 큐에 넣음.

6. 큐가 비지 않을 때 까지 BFS탐색.

1. 큐의 맨 앞에 있는 좌표 및 해당 좌표까지 걸린 시간을 저장해두고 pop한다.
2. 상, 하, 좌, 우 탐색을 한다. idx가 올바르고, 방문한 적이 없고, 벽이 아니라면 해당 칸을 방문처리 한 후에 큐에 집어넣는다. 만일 해당 칸이 바이러스 칸이라면 집어넣기만 하고, 빈 칸이었다면 tmpEmpty 값을 1 빼준다.
3. 현재 칸에 대한 조사가 끝난 후에, 만일 현재 칸이 원래 바이러스가 아니었다면, retTime을 curTime과 비교해서 더 큰 값으로 갱신해준다. 바이러스가 아닐 때만 갱신해 주는 이유는 바이러스를 활성화 해주는 것은 빈 칸을 바이러스 채우는 것이 아니기 때문에 시간적으로 의미가 있는 것은 아니다.
4. 그리고 현재 칸을 curTime으로 만들어준다.
5. 만일 tmpEmpty가 0, 모든 빈 칸을 바이러스로 퍼뜨렸다면 retTime을 반환하고 아니라면 -1을 반환한다.

처음에 풀었을 때는 자꾸 이상하게 나와서 못풀었었는데 집에 와서 싹 다 갈아엎으려다가 조금 손보니까 바로 맞춘 문제.

운이 좋았던 것 같다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.