백준 14502번 연구소 문제 C++

오늘은 백준 14502번 연구소 문제를 풀어보았습니다,

문제를 풀던 중 이 문제는 더 높은 BFS/DFS 이해도를 위해서 복기하는게 좋다고 느껴져서 글을 남기게 됐습니다.

우선 제가 생각하는 이 문제의 주요 키워드들입니다.

1. 벽 생성이 가능한 공간들을 찾는다
2. 무작위로 세 개의 벽을 생성한다
3. 생성된 Map에 바이러스를 퍼트려본다
4. 매번 카운트를 세어준다

풀이

for (int i = 0; i < n; i++) {
   	for (int j = 0; j < m; j++) {
    	int c;
    	cin >> c;
    	arr[i][j] = c;
    		
    	if (c == 2) virus.push_back({i, j});
    	if (c == 0) wall.push_back({i, j});
	}
}

우선 입력을 받습니다
이 때 바이러스는 퍼트려줘야 하기에 따로 리스트를 만들어 저장합니다,
또한 벽이 생성 가능한 공간도 리스트를 만들어 저장합니다.

for (int i = 0; i < wall.size(); i++) {
    for (int j = 0; j < i; j++) {
    	for (int k = 0; k < j; k++) {
    		arr[wall[i].first][wall[i].second] = 1;
    		arr[wall[j].first][wall[j].second] = 1;
    		arr[wall[k].first][wall[k].second] = 1;
    		ret = max(ret, cal());
   			arr[wall[i].first][wall[i].second] = 0;
   			arr[wall[j].first][wall[j].second] = 0;
   			arr[wall[k].first][wall[k].second] = 0;
		}
	}
}

이후 무작위로 벽이 생성 가능한 위치에 벽을 만들어 줍니다.
이때 벽을 만든 후 바이러스를 퍼트린 후 남은 공간의 수를
매번 카운트 후 다시 벽을 없애주어야 합니다

int cal() {
	memset(visited, 0, sizeof(visited));
	
	for (pair<int, int> a : virus) {
		bfs(a.first, a.second);
	}
	
	int cnt = 0;
	for (int i = 0; i < n; i++) {
    	for (int j = 0; j < m; j++) {
    		if (arr[i][j] != 0 && visited[i][j]) continue; 
            cnt++;
		}
	}

	return cnt;
}

계산할 때마다 visited는 다시 초기화 해주어야 하며
바이러스가 여러개 일 수 있으니 하나씩 퍼트려줍니다

다 퍼트린 후 전체적으로 맵을 돌면서 살아있는 공간들을 체크해주는데
이때 방문한 곳들은 이미 바이러스가 퍼진 곳이니 continue 합니다

void bfs(int x, int y) {
    q.push({x, y});
    visited[x][y] = 1;
    
    while(q.size()) {
    	int x = q.front().first;
    	int y = q.front().second;
    	q.pop();
    	
    	for (int i = 0; i < 4; i++) {
    		int nx = x + dx[i];
    		int ny = y + dy[i];
    		
    		if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue;
    		if (arr[nx][ny] == 1) continue;
    		visited[nx][ny] = 1;
    		q.push({nx, ny});
		}
	}
}

이후 바이러스에 맞춰 BFS를 돌려주는데
이미 벽인 경우와 방문한 경우(바이러스가 퍼진 경우)는 continue 합니다.

 cout << ret << '\n';

그렇게 나온 결과를 출력해줍니다.

이 문제를 복기하게 된 가장 큰 이유는
시간 복잡도 계산을 하는 습관을 들여놔야겠다는 깨달음을 주었습니다

가장 처음 브루트포스로 풀 수 없는 알고리즘인줄 알고 어떤식으로 벽을
세워야 하는지 매우 많은 고민을 했고 결국 힌트를 본 후 풀 수 있었습니다

하지만 힌트를 본 후 이렇게 무식하게 하나씩 세워도 된다는 점에서 놀랐으며
앞으로 문제를 풀 때 더 섬세함이 필요하다는 점을 새기기 위해 포스트를 작성했습니다,
감사합니다.

전체코드입니다

#include <bits/stdc++.h>

using namespace std;

int n, m, ret;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int arr[10][10];
int visited[10][10];
queue<pair<int, int>> q;
vector<pair<int, int>> virus;
vector<pair<int, int>> wall;

void bfs(int x, int y) {
    
    q.push({x, y});
    visited[x][y] = 1;
    
    while(q.size()) {
    	int x = q.front().first;
    	int y = q.front().second;
    	q.pop();
    	
    	for (int i = 0; i < 4; i++) {
    		int nx = x + dx[i];
    		int ny = y + dy[i];
    		
    		if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) continue;
    		if (arr[nx][ny] == 1) continue;
    		visited[nx][ny] = 1;
    		q.push({nx, ny});
		}
	}
}

int cal() {
	memset(visited, 0, sizeof(visited));
	
	for (pair<int, int> a : virus) {
		bfs(a.first, a.second);
	}
	
	int cnt = 0;
	
	for (int i = 0; i < n; i++) {
    	for (int j = 0; j < m; j++) {
    		if (arr[i][j] == 0 && !visited[i][j]) cnt++;
		}
	}
	
	return cnt;
}

int main() {
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < m; j++) {
    		int c;
    		cin >> c;
    		arr[i][j] = c;
    		
    		if (c == 2) virus.push_back({i, j});
    		if (c == 0) wall.push_back({i, j});
		}
	}
    
    for (int i = 0; i < wall.size(); i++) {
    	for (int j = 0; j < i; j++) {
    		for (int k = 0; k < j; k++) {
    			arr[wall[i].first][wall[i].second] = 1;
    			arr[wall[j].first][wall[j].second] = 1;
    			arr[wall[k].first][wall[k].second] = 1;
    			ret = max(ret, cal());
    			arr[wall[i].first][wall[i].second] = 0;
    			arr[wall[j].first][wall[j].second] = 0;
    			arr[wall[k].first][wall[k].second] = 0;
			}
		}
	}
    
    cout << ret << '\n';
    
    
    return 0;
}