<Baekjoon> #17142 BFS,DFS_Lab3 c++

#17142 연구소3
이전에 거의 비슷한 문제#14502 연구소를 풀어본 적이 있었다

문제를 풀 때 미처 생각지 못한 조심해야하는 부분들이 있어서 문제를 해결하는데 상당히 오랜 시간이 걸렸다.

1. Initialize

• 먼저 연구소의 모든 칸에 빈칸과 바이러스를 입력하며 빈칸의 갯수(emptySize)와 바이러스가 있는 좌표들을 virus벡터에 저장해준다

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		cin >> lab[i][j];
		if (lab[i][j] == VIRUS) 
			virus.push_back(make_pair(i, j));
		else if (lab[i][j] == EMPTY)
			emptySize++;
	}
}

2. makeActive - 바이러스 활성화

• 전체 바이러스에서 i번째 바이러스를 활성화시킨다
  (lab[y][x]==3이면 활성화된 상태이다)
• M개의 바이러스가 활성화 되면 bfs함수에서 바이러스가 퍼진다

void makeActive(vector<vector<int>> lab, int idx, int cnt) {
	int y = virus[idx].first;
	int x = virus[idx].second;
	lab[y][x] = ACTIVE;

	if (cnt == M) {
		bfs(lab);
		return;
	}
	for (int i = idx + 1; i < virus.size(); i++)
		makeActive(lab, i, cnt + 1);
}

• 바이러스 활성화 화는 부분은 dfs를 이용해 순열을 구하는 방식으로 하면 된다. 참고로 다른 사람의 코드를 보았을 때 bool select[10]배열을 두고

void makeActive(int idx, int cnt) {
	if (cnt==M) {

    //M개의 바이러스 활성화 후 Queue에 담고 bfs함수 호출
    ..........
    }

  for (int i=idx; i<virus.size(); i++) {
      if (selected[i]) continue;
      selected[i]=true;
      makeActive(i+1, cnt+1);
      selected[i]=false;
  }
}

이렇게 구현하는 방법도 있다

3. bfs() - 바이러스가 퍼지는 부분

• 먼저 lab의 모든 좌표를 돌며 바이러스가 활성화된 좌표 즉,lab[i][j]==ACTIVE에서 (i,j)를 모두 큐에 넣어준다

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (lab[i][j] == ACTIVE) {
				q.push(make_pair(i, j));
				dist[i][j] = 0;
			}
		}
	}

• 큐에서 하나씩 빼주면서 큐에 4방향으로 인접한 곳에 벽이 아니고 한 번도 방문한 적이 없다면 다시 큐에 넣어주는 것을 반복한다
• lab[i][j]==EMPTY였는데 바이러스가 퍼지면 infectSize를 늘려주어 앞에서 탐색이 끝난 후 emptySize와 같은지 비교하여 모든 빈 공간에 바이러스가 퍼졌는지 확인한다
• lastSec 변수를 두어 마지막으로 EMPTY공간에 바이러스가 퍼질 때 몇 초째였는지 저장해준다
  (이미 VIRUS였는데 ACTIVE상태가 될 때는 lastSec을 변화시키지 않는다.)
  
  위와같이 (0,0)위치에 있는 바이러스만 활성화 시킨다고 하자. dist를 보면 제일 끝에 있는 바이러스까지 활성화 바이러스가 되려면 6초의 시간이 걸리지만 lab은 처음부터 모든 칸에 바이러스가 있기 때문에 문제에서 원하는 모든 칸에 바이러스를 퍼뜨리는 시간은 0초가 된다. 따라서 EMPTY에서 ACTIVE상태가 될 때만 lastSec을 갱신하고 VIRUS에서 ACTIVE상태가 될 때는 갱신하지 않는다.

for (int dir = 0; dir < 4; dir++) {
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
	
	//벽이 아니고 한 번도 방문된 적이 없을 때
	if (lab[ny][nx] != WALL && dist[ny][nx]==-1) {
		dist[ny][nx] = dist[y][x] + 1;

        //원래 빈 공간이었는데 바이러스가 침입하여 ACTIVE상태가 된다면
		if (lab[ny][nx] == EMPTY) {
			infectSize++;
			lastSec = dist[ny][nx];
		}
		lab[ny][nx] = ACTIVE;
		q.push(make_pair(ny, nx));
	}
}

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int EMPTY = 0;
const int WALL = 1;
const int VIRUS = 2;
const int ACTIVE = 3;

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

int emptySize = 0;
int N, M;
vector<pair<int, int>> virus;

void bfs(vector<vector<int>>& lab) {
	int infectSize = 0;
	int lastSec = 0;
	queue<pair<int, int>> q;
	vector<vector<int>> dist = vector<vector<int>>(N, vector<int>(N, -1));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (lab[i][j] == ACTIVE) {
				q.push(make_pair(i, j));
				dist[i][j] = 0;
			}
		}
	}
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

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

			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;

			if (lab[ny][nx] != WALL && dist[ny][nx]==-1) {
				dist[ny][nx] = dist[y][x] + 1;
				if (lab[ny][nx] == EMPTY) {
					infectSize++;
					lastSec = dist[ny][nx];
				}
				lab[ny][nx] = ACTIVE;
				q.push(make_pair(ny, nx));
			}
		}
	}

	if (infectSize==emptySize) 
		minSec = min(minSec, lastSec);
}
void makeActive(vector<vector<int>> lab, int idx, int cnt) {
	int y = virus[idx].first;
	int x = virus[idx].second;
	lab[y][x] = ACTIVE;

	if (cnt == M) {
		bfs(lab);
		return;
	}
	for (int i = idx + 1; i < virus.size(); i++)
		makeActive(lab, i, cnt + 1);
}

void init() {
	cin >> N >> M;
	vector<vector<int>> lab = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> lab[i][j];
			if (lab[i][j] == VIRUS) 
				virus.push_back(make_pair(i, j));
			else if (lab[i][j] == EMPTY)
				emptySize++;
		}
	}
	for (int i = 0; i < virus.size(); i++)
		makeActive(lab, i, 1);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	init();
	if (minSec == 0x7fffffff) cout << -1 << endl;
	else
		cout << minSec << endl;
	return 0;
}

실수했던 점

• 비활성화 바이러스가 활성화 바이러스와 접촉하면 활성화 바이러스가 된다는 것을 빼먹고 원래 바이러스인 부분은 아예 queue에 넣지 않았다.
• 비활성화 바이러스가 있던 부분은 원래 바이러스였으니까 활성화 바이러스로 변한다 해도 시간을 늘릴 필요가 없다는 것
• dist를 초기화 할 때 -1로 하지 않고 0으로 초기화 했던 것

쉬운문제라 생각했는데 시행착오가 많았다. 새벽까지 풀다가 도저히 안 돼서 잠들고 다음날 아침에 다시 푼 문제 ㅠㅠ