[백준] 31791 바이러스 공격 C++

1. 문제 설명

• 문제 링크 : https://www.acmicpc.net/problem/31796
• 부산대학교 2024 pnup div1 / div2 기출문제 

---

2. 풀이 과정

• 문제 해결의 흐름

1. 입력 받을 때 바이러스 위치들을 전부 queue에 저장하자
2. bfs 구현 
   • q_virus와 q_building, 둘 중 하나가 빌 때까지 bfs 탐색이 이루어진다.
   • Tg의 시간동안 virus가 감염시키는 것이 building이 완전히 감염되는 것보다 우선시되어야 한다. 
   • virus의 상하좌우에 building이 위치해 있다면 해당 building은 감염되었기에 q_building에 push해주자
   • virus의 상하좌우에 안전지역이 위치해 있다면 해당 안전지역은 감염되어 virus가 되었기에 q_viurs에 push해주자
   • q_building의 값들 중 바이러스의 전이가 끝난 값들은 virus 취급해주자. (cur_time + Tb + 1의 시간이 지난 값들)

• 코드 

#include <iostream>
#include <queue>

using namespace std;

struct q_val {
    int row;
    int col;
    int time;
};

int dr[4] = {0,0,-1,1};
int dc[4] = {1,-1,0,0};

int R, C;
int Tg, Tb, X, B;
char pnuMap[1001][1001];
queue<q_val> q_virus;
queue<q_val> q_building;
int visited[1001][1001] = {};
int virus[1001][1001] = {};

q_val search() {
    if (q_virus.empty()) {
        q_val ret_val = q_building.front();
        q_building.pop();
        return ret_val;
    }

    if (q_building.empty()) {
        q_val ret_val = q_virus.front();
        q_virus.pop();
        return ret_val;
    }

    // building가 감염되는 것이 virus가 감염시키는 것보다 우선시되어야 한다.
    int virus_time = q_virus.front().time;
    int building_time = q_building.front().time;
    if (virus_time < building_time) {
        q_val ret_val = q_virus.front();
        q_virus.pop();
        return ret_val;

    } else {
        q_val ret_val = q_building.front();
        q_building.pop();
        return ret_val;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // 1. 입력 받기
    cin >> R >> C;
    cin >> Tg >> Tb >> X >> B;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> pnuMap[r][c];
            if (pnuMap[r][c] == '*') { // 초기 바이러스 위치
                q_val firs_val = {r,c,0};
                q_virus.push(firs_val);
                visited[r][c] = 1;
            }
        }
    }

    // 2. bfs 구현
    while(!q_virus.empty() || !q_building.empty()) {
        q_val current_val = search();
        int cur_row = current_val.row;
        int cur_col = current_val.col;
        int cur_time = current_val.time;

        if (cur_time > Tg) break;

        virus[cur_row][cur_col] = 1;
        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int next_r = cur_row + dr[i];
            int next_c = cur_col + dc[i];

            if (next_r < 0 || next_r >= R || next_c < 0 || next_c >= C) continue;
            if (visited[next_r][next_c]) continue;

            visited[next_r][next_c] = 1;

            if (pnuMap[next_r][next_c] == '#') {
                q_val next_val = {next_r,next_c,cur_time + Tb + 1};
                q_building.push(next_val);
            } else if (pnuMap[next_r][next_c] == '.') {
                q_val next_val = {next_r,next_c,cur_time + 1};
                q_virus.push(next_val);
            }
        }
    }

    // 3. 출력하기
    bool safe = false;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (virus[r][c] == 0) {
                safe = true;
                cout << r + 1 << " " << c + 1 << "\n";
            }
        }
    }
    if (!safe) cout << -1 << "\n";

    return 0;
}

• 이 문제를 통해 얻어갈 수 있는 것들

1.  endl; 이 아닌 "\n"; 사용해주기! endl은 개행 문자를 출력하는 것 뿐만 아니라 출력 버퍼를 비워주는 반면에 "\n"은 개행 문자만을 출력하고 출력 버퍼를 비우지 않기에 성능이 향상된다. 
2.  ios::sync_with_stdio(false); 사용해주기!  cin과 cout을 C의 표준 입출력 함수인 scanf와 printf와 동기화하지 않도록 하여 입출력 성능을 향상시킨다.
3. cin.tie(NULL); 사용해주기!  cin과 cout이 동기화될 때 발생되는 버퍼링을 제어한다. 기본적으로 cin과 cout은 동기화되어 있어 cin으로 데이터를 입력 받을 때마다 cout의 버퍼를 비워준다. 하지만 이는 입출력 작업이 많은 경우에 성능적으로 영향을 끼친다.
4. cout.tie(NULL); 사용해주기!  cout의 출력 버퍼링을 제어한다. 기본적으로 cout은 endl을 만날 때마다 버퍼를 비우기 때문에 출력이 즉시 화면에 나타나기에 cout.tie(NULL)을 사용하여 이러한 버퍼링을 해제해 성능을 향상시킬 수 있다. 
5. 시간복잡도의 기준은 항상 최악의 경우를 기준으로 설정하자. 위의 풀이같은 경우 O(N*M)의 시간복잡도를 가진다. 
6. 1시간 내에 못 풀면 못 푸는 문제이다. 
7. 구조체 메모리 할당의 이해 (아래 링크 참고)

https://velog.io/@d2h10s/CC-Struct%EC%9D%98-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%9D%B4%ED%95%B4

---

3. 후기 

 사실 이 문제때문에 이틀을 날렸다 ㅠㅠ... 최근 bfs 문제만 팠기에 bfs 문제는 정말 자신 있었는데 벽을 느꼈다. 

고통의 흔적들....

 

 특히 분명 알맞게 구현한 거 같은데 40%에서 시간초과로 틀려서 너무 절망적이었다. 당시 나의 코드는 다음과 같다.

//
// 1. 처음 입력 받을 때 바이러스 위치들을 전부 queue에 저장하자.
// 2. 바이러스가 전파되는 총 시간 Tg 동안 bfs를 통해 바이러스 위치 주변, 상하좌우를 감염시키자.
//    (1) 건물을 찾았다면? 처음 찾았다면 빌딩 queue에 저장. 건물에 이미 바이러스가 다 퍼졌다면 앞으로 건물이 아닌 바이러스로 보기.
//    (2) 안전지대를 찾았다면? 바로 감염시키기
// 3. 빌딩 queue를 탐색하며 건물에 감염 스택 쌓기

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct building_val {
    int r;
    int c;
    int cnt;
};

int dr[4] = {0,0,-1,1};
int dc[4] = {1,-1,0,0};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 입력 받기
    int R, C;
    int Tg, Tb, X, B;
    cin >> R >> C;
    cin >> Tg >> Tb >> X >> B;
    vector<std::vector<char> > pnuMap(R+1, std::vector<char>(C+1));
    vector<std::vector<int> > visited(R+1, std::vector<int>(C+1, 0));
    queue<pair<int, int> > q_virus;
    queue<building_val> q_building;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> pnuMap[r][c];
            if (pnuMap[r][c] == '*') { // 초기 바이러스 위치
                q_virus.push(make_pair(r,c));
            }
        }
    }

    B = 0;
    // 구현
    for (int t = 1; t <= Tg; t++) {
        // 바이러스가 감염시킴
        int virus_cnt = X;
        while(virus_cnt--) {
            int cur_r = q_virus.front().first;
            int cur_c = q_virus.front().second;
            X -= 1;
            q_virus.pop();
            // 상하좌우 탐색
            for (int i = 0; i < 4; i++) {
                int next_r = cur_r + dr[i];
                int next_c = cur_c + dc[i];

                if (next_c < 0 || next_r < 0 || next_c > C || next_r > R) continue;
                if (pnuMap[next_r][next_c] == '#' && visited[next_r][next_c] != 1) { // 건물 처음 방문
                    visited[next_r][next_c] = 1;
                    building_val new_val = {next_r,next_c,0};
                    q_building.push(new_val);
                    B += 1;
                } else if (pnuMap[next_r][next_c] == '.'){ // 안전한 구역 바로 감염!
                    pnuMap[next_r][next_c] = '*';
                    q_virus.push(make_pair(next_r,next_c));
                    X += 1;
                }
            }
        }



        // 건물에 감염 스텍 쌓기
        int building_cnt = B;
        while(building_cnt--){
            int cur_r = q_building.front().r;
            int cur_c = q_building.front().c;
            int cur_cnt = q_building.front().cnt;
            q_building.pop();

            // 바이러스 감염 끝
            if (cur_cnt == Tb) {
                pnuMap[cur_r][cur_c] = '*';
                q_virus.push(make_pair(cur_r,cur_c));
                X += 1;
                B -= 1;
            } else {
                cur_cnt += 1;
                building_val cur_val = {cur_r, cur_c, cur_cnt};
                q_building.push(cur_val);
            }
        }


    }


    // 안전한 구역 출력
    int safe_count = 0;
    for (int r = 0; r < R; ++r) {
        for (int c = 0; c < C; ++c) {
            if (pnuMap[r][c] != '*') {
                cout << r + 1 << " " << c + 1 << "\n";
                safe_count++;
            }
        }
    }
    if (safe_count == 0) cout << -1 << "\n";


    return 0;
}

 

 언뜻 보면 정확히 구현한 것처럼 보이지만 시간 초과를 극복하지 못한 허접 코드에 불과하다. 참고로 위의 코드는 O(N**2)의 시간복잡도를 가진다. 시간복잡도를 낮추기 위해 2중 반복문이 아닌 한 번의 반복문을 통해 bfs를 구현하고자 하였다. 그렇기에 virus와 building의 큐를 분리하고 시간을 비교하여 더 우선적으로 처리해야하는 값들을 처리해주었다. 

 

 오기가 생겨서 계속 팠던 거 같은데 왠만하면 문제 풀이에 1시간 이상 쏟아 붓지 말아야겠다 ㅠ..