6주차(DFS와 BFS) - [C++]백준14502 연구소

12 Apr 2022 in Study on Algorithm

백준14502 연구소 링크

문제

예제 입력

---

코드

#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int n, m, result = 0;
int map[8][8];
int temp[8][8];
vector<pair<int, int>> poison;

// 방향 이동
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void dfs(int x, int y) {
    if (temp[x][y] == 1) return;
   
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < m) {
            if (temp[nx][ny] == 0) {
                temp[nx][ny] = 2;
                dfs(nx, ny);
            }
        }
    }
}

void bfs() {
    queue<pair<int, int>> q;
    for (int i = 0; i < poison.size(); i++)
        q.push(poison[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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (temp[nx][ny] == 0) {
                    temp[nx][ny] = 2;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
}

int counter() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (temp[i][j] == 0)
                cnt += 1;
        }
    }
    return cnt;
}

void wall(int x, int depth) {
    if (depth == 3) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                temp[i][j] = map[i][j];
            }
        }

        //bfs();
        for (int i = 0; i < poison.size(); i++) {
            dfs(poison[i].first, poison[i].second);
        }

        result = max(result, counter());
        return;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0) { // 빈공간 일 경우
                map[i][j] = 1; // 벽 세우기 
                wall(i, depth + 1); // 세운 벽 수 증가 
                map[i][j] = 0; // 초기화 
            }
        }
    }
}

int main(void) {
    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)
                poison.push_back(make_pair(i, j));
        }
    }

    wall(0, 0);
    cout << result;
}

설명

이 문제는 연구소에 바이러스가 발생하여 확산되지 전에 벽을 세워서 최소한의 오염으로 안전구역 크기의 최대값을 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 Queue를 사용하여 구현했습니다. 연구소에 대한 정보를 입력 받고 먼저 정해진 수의 벽을 세우고 그 후에 따로 저장한 오염물질의 좌표를 기준으로 확산하는데 BFS 또는 DFS를 변형하여 두 가지 경우로 구현했습니다. BFS는 너비우선 탐색으로 나선형 모습으로 탐색하고 DFS는 깊이우선 탐색으로 특정 방향으로 나가는 모습으로 탐색을 합니다. 그리고 check값을 배정하는데 이것은 같은 곳을 탐색할 수 있는 것을 방지합니다. 결과값은 벽이 어떻게 세워지냐에 따라 다르기 때문에 최대값을 갱신하며 출력했습니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과