[백준 14502] - 연구소(구현) C++

문제

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

14502번: 연구소

접근방법

이 문제를 푸는 방법은 다음과 같다.

1. 벽 세 개를 설치한다.

2. 바이러스를 확산시킨다.

3. 안전영역의 크기를 구한다.

 

내가 가장 많이 고민했던 부분은 벽 세 개를 설치하는 방법이다.

 

벽 세 개를 설치한 후에 거기에 바이러스를 퍼뜨려야 하기 때문에, 벽을 세운 좌표에 visited표시를 해줘야하고, 다음 벽 세 개를 고르기 위해서 마지막으로 설치한 벽 세 개를 삭제하고 다시 설치해야한다. 이를 구현하는 방법을 고민했다.

 

결론부터 말하자면, 나는 재귀함수로 풀었다. 다른 풀이에는 3중첩 for문을 활용하는 것도 있었다. 3중첩 for문을 사용하는 방법은 다음과 같다.

1. 이동할 좌표를 1차원 배열에 pair를 이용해서 저장.

2. for (int i=0;i<배열사이즈;i++) for (int j=0;j<i;j++) for (int k=0;k<j;k++) 의 3 중첩 for 문 사용.

3. 배열에서 i번째, j번째, k번째 원소를 뽑아냄.

 

위 방법은 내가 생각하지 못했던 방법이다. 나중에 잘 써먹어야 겠다.

 

중첩 for문으로 풀 때는 for문안에서 visited를 세 개 전 부 한꺼번에 넣었다 뺐다 해야한다.

재귀함수로 풀 때는 아래와 같이 구현할 수 있다. 재귀함수로 구현하는 것이 더 확장성이 있고, 코드도 간단하다.

 

바이러스를 확산시킬 때는 넣고 다 뺄 수 가 없었다. 안전 영역을 세야하기 때문에, dfs를 돌리고 나서 바이러스가 그래프에 있어야했다.

그래서 따로 virousOnly라는 바이러스만 넣은 배열을 추가했다. 코드가 다소 복잡해졌지만, 다른 방법이 생각나지 않았다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 

int n, m;
int graph[8][8];
int visited[8][8] = {0,};
int virousOnly[8][8] = {0,};
const int dy[] = {0, 0, -1, 1};
const int dx[] = {-1, 1, 0, 0};

void dfs(int y, int x) {
    for (int i=0;i<4;i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny >= 0 && ny < n && nx >= 0 && nx < m && !visited[ny][nx]
        && !virousOnly[ny][nx] && graph[ny][nx] == 0) {
            virousOnly[ny][nx] = 2;
            dfs(ny, nx);
        }
    }
}

int bruteForce(int depth) {
    int ret = 0;
    //벽 세 개를 세운 상태
    if (depth == 0) {       
        //바이러스를 찾아서 확산시킴.
        memset(virousOnly, 0, sizeof(virousOnly));
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (graph[i][j] == 2) {
                    virousOnly[i][j] = 2;
                    dfs(i, j);
                }
            }
        }

        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                if (graph[i][j] == 0 && visited[i][j] == 0 && virousOnly[i][j] == 0) ret++;
            }
        }
        return ret;
    }

    for (int i = 0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (!visited[i][j] && graph[i][j] == 0) {      //벽을 세우는 곳은 0이어야 함.
                visited[i][j] = 1;
                ret = max(ret, bruteForce(depth-1));
                visited[i][j] = 0;
            }
        }
    }
    return ret;
}

int main() {
    int ret = 0;
    cin >> n >> m;
    FOR(i, n) FOR(j, m) {
        cin >> graph[i][j];
    }
    ret = bruteForce(3);
    cout << ret << endl;
    return 0;
}

개선할 점

아직 많이 부족함을 느낀다. 특히 기본기가 많이 부족한 거 같다.

처음부터 다시 배운다는 마음가짐으로 공부해야겠다.