[BOJ 14502] 연구소

문제출처

https://www.acmicpc.net/problem/14502

문제풀이

진짜 시간이 오래걸렸다. 기둥을 세울때 조건을 잘못줘서 자꾸 예외상황이 발생했기 때문이다. 
반복을 줄이려는 생각만 앞서다 정확한 조건을 생각못했다. 
dfs(기둥세우기) 함수에서 x와 y값을 인자로 받아 
x, y부터 for문을 돌리면 된다 생각했는데 x는 가능하지만 y는 불가능 하다. 
왜냐하면 (예제2번의 경우) 최적의 기둥이 (1,5) / (2,4) / (4,4) 인데 
(1,5) 기둥을 세우면 (2,4) 기둥을 세우지 못하기 때문이다. 
dfs를 제대로 이해했다면 이런실수는 없었을텐데 너무 코드만 구조화해서 외워둔 탓인가..ㅠㅠ
결국 0부터 완탐하다가 x만 인자로 넘겨주면 된다는 것을 깨닫고 재제출한 문제...
 
문제풀이는 다음과 같으며 이 문제도 단계를 나눠서 풀이했다. 
 
case 1) 모든 경우에 3개의 기둥을 세운다(dfs)
case 2) 기둥을 세운 map을 복사해둔다. (모든 경우에 대해서 풀어야 하기 때문에 원본이 필요합니다.)
case 3) 복사한 map에 바이러스를 전파시킨다.(bfs)
case 4) 바이러스 전파가 완료되면 0(안전지역)의 갯수를 세어준다. (bfs 아래의 반복문)
 
이과정을 반복하여 풀이하면된다. 바이러스의 초기 위치를 알기위해 
map을 입력받을 때 virus 벡터에 좌표를 넣어주었지만
이과정은 bfs 반복문안에 if(map[i][j] == 2)조건을 주어 위치를 알아낼 수도 있다. 
저는 반복문을 한번 더 돌리기 싫어서 입력할때 받아두었지만 
성능상 그리 크게 차이가 나지는 않을 듯하다.
안전지역의 갯수를 max함수를 통해 큰값을 result에 넣어주고 출력하면 끝!
아! 바이러스를 전파시킬때 bfs를 쓴 이유는 
어디서 bfs는 탐색을 하면서 행위가 이루어질때 좋은 방법이라 주워들었기 때문이다. (정확하지는 않아요 ㅠㅠ)
자세한건 dfs / bfs를 다시 공부하고 문제풀이를 많이해본 후 체득하고 다시 포스팅 하겠습니다.
 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 8
 
using namespace std;
 
int n,m,result;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int map[MAX][MAX];
vector<pair<int, int> > virus;
 
void copyMap(int (*src)[MAX], int (*dest)[MAX]) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            dest[i][j] = src[i][j];
        }
    }
}
 
void bfs() {
    int copy[MAX][MAX];
    copyMap(map, copy);
 
    queue<pair<int, int> > q;
    for(int i=0; i<virus.size(); i++)
        q.push(virus[i]);
 
    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(copy[nx][ny]==0) {
                copy[nx][ny]=2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    int tmp=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(copy[i][j]==0)
                tmp++;
        }
    }
 
    result = max(result, tmp);
}
 
void dfs(int x, int cnt) {
    if(cnt==3) {
        bfs();
        return;
    }
 
    for(int i=x; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(map[i][j]==0) {
                map[i][j]=1;
                dfs(i, cnt+1);
                map[i][j]=0;
            }
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin>>map[i][j];
            if(map[i][j]==2)    
                virus.push_back(make_pair(i,j));
        }
    }
 
    dfs(0, 0);
    cout<<result;
    return 0;
}

추가로 생각해본 방법

먼저 입력받을때 0의 갯수를 모두 세어준 뒤
dfs(기둥세우기)에서 3개를 빼준다. 이후 바이러스가 전파될때마다 1씩 빼주면 
0을 카운트 하는 2중 for문을 없앨 수 있다.