[C++] 백준 14502 : 연구소
#include <iostream>
#include <algorithm> // max, copy
#include <utility> // pair
#include <queue> // bfs
using namespace std;
int map[9][9]; // 연구소 맵 0 : 빈 칸, 1 : 벽, 2 : 바이러스
int tmp[9][9]; // 감염시킬 임시 값
queue<pair<int, int> > q; // x, y
int maxNum = -1; // 최대값 저장
//상하좌우 탐색
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int N, M; // 세로, 가로
void BFS(){ // 인접한 곳부터 바이러스 퍼지기 때문에 BFS 사용
//바이러스 탐색 계속 해줘야 함. main에서 처음 넣은 q 다 빠지면 탐색 못하기 때문에
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
if(tmp[i][j] == 2){
q.push({i, j}); // 바이러스 있는 경우 큐에 넣기
}
}
}
while(!q.empty()){ // 큐 빌 때까지 계속
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 || ny <= 0 || nx > N || ny > M){ // 맵 밖으로 나갈 경우
continue;
}
if(tmp[nx][ny] == 0){ // 인접항에 빈 공간 있는 경우
tmp[nx][ny] = 2; // 바이러스 감염
q.push({nx, ny}); // 새 노드 큐에 넣기
}
}
}
int cnt = 0;
//printf("*******\n");
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
if(tmp[i][j] == 0){
cnt++; // 안전지대 수 세기
}
//printf("%d ", tmp[i][j]);
}
//printf("\n");
}
maxNum = max(cnt, maxNum);
return;
}
void DFS(int wall){ // 백트래킹 - 수 많은 경우 중 순열 찾는 것 처럼
if(wall == 0){ // 벽 다 세워지면
copy(&map[0][0], &map[0][0] + 81, &tmp[0][0]); //맵에 임시값 복사해넣기
BFS(); // 바이러스 퍼뜨리기
return;
}
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){ // 범위 조심 0~N-1까지인지 1~N까지인지
if(map[i][j] == 0){ // 빈 공간 있으면
map[i][j] = 4; // 벽세우기
DFS(wall - 1); // 백트래킹으로 탐색
map[i][j] = 0; // 초기화
}
}
}
}
int main(int argc, char** argv){
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
scanf("%d", &map[i][j]); // 맵 입력받기
}
}
DFS(3); // 벽 3개 세워야 함
printf("%d", maxNum); //최대 안전 지대 수 출력
return 0;
}
-
메모리 제한 또는 시간 제한이 걸릴까봐 걱정되었는데 512MB, 2초정도면 모든 임시값을 copy해도 괜찮을 정도라는 것을 알게 되었다.
-
벽 3개 세우기는 백트래킹(DFS)를 이용한다. 순열을 구하는 것과 같다. 모든 경우의 수에서 3개씩 뽑아 줄세우면 된다.
-
STL 라이브러리의 algorithm을 사용하면 copy를 한 줄에 끝낼 수 있다. copy(copy할 것의 첫 주소, copy할 것의 마지막 주소, copy해 넣을 곳의 주소)를 입력하면 된다. 이차원 배열의 경우
copy(&map[0][0], &map[0][0] + 81, &tmp[0][0]);
처럼 사용한다는 것을 잊지 말자
-
바이러스 감염은 인접된 부분부터 시작한다. 따라서 BFS를 이용하여 계속 탐색해나가는 것이 좋다. 큐를 사용해서 조건에 만족하면 push 하고 q가 빌 때 까지 계속 pop하면서 인근을 탐색한다.
-
main 문에서 바이러스에 감염된 노드를 큐에 넣는 것으로는 충분하지 않다. 모든 경우의 수를 탐색하기에 BFS에서 계속 감염된 노드가 있는지를 확인해서 넣어주어야한다.
-
for문 돌릴 때 주의하자. 0~N-1까지 탐색할지, 1~N까지 탐색할지. 은근 많이하는 실수이다.
Author And Source
이 문제에 관하여([C++] 백준 14502 : 연구소), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-14502-연구소저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)