백준 18405번 [경쟁적 전염](C++) -yes6686- 티스토리

백준 문제 풀이: 18405 (경쟁적 전염)

---

문제 링크: https://www.acmicpc.net/problem/18405

문제 설명:

N×N 크기의 시험관에 바이러스가 퍼져 있습니다. 각 칸에 바이러스 종류가 주어지며, 바이러스는 매 초마다 상하좌우로 증식합니다. - 낮은 번호의 바이러스가 먼저 증식합니다. - 주어진 시간 S 후, 특정 좌표 (X, Y)에 어떤 바이러스가 있는지를 출력해야 합니다. 만약 해당 칸에 바이러스가 없다면 0을 출력합니다.

---

문제 해결 코드

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

int n, k, s, x, y;
int arr[201][201];
int dx[4] = {0, 0, 1, -1}; // 상하좌우 이동
int dy[4] = {1, -1, 0, 0};

// 바이러스 정보 저장: {시간, 바이러스 번호, x좌표, y좌표}
queue> q;

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

    cin >> n >> k;

    // 바이러스의 초기 위치를 큐에 삽입
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] != 0) {
                q.push({0, arr[i][j], i, j}); // 초기 시간 0
            }
        }
    }

    cin >> s >> x >> y; // 시간 S와 좌표 X, Y

    // BFS를 이용한 확산
    while (!q.empty()) {
        int time, virus, cx, cy;
        tie(time, virus, cx, cy) = q.front();
        q.pop();

        // S초가 지나면 종료
        if (time == s) break;

        // 네 방향으로 확산
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && arr[nx][ny] == 0) {
                arr[nx][ny] = virus; // 바이러스 확산
                q.push({time + 1, virus, nx, ny});
            }
        }
    }

    // 결과 출력
    cout << arr[x][y] << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: BFS(너비 우선 탐색)를 사용해 낮은 번호의 바이러스부터 확산시키며 시간 단위로 전파합니다.
• 구현 세부사항:
  • queue: 바이러스의 확산 순서를 유지합니다. 각 큐 항목에는 (현재 시간, 바이러스 번호, 좌표)를 저장합니다.
  • 바이러스가 퍼진 곳은 arr에 기록되며, 이미 확산된 칸은 다시 방문하지 않습니다.
  • 시간 S가 지나거나 큐가 비면 탐색을 종료하고 결과를 출력합니다.
• 시간 복잡도 분석:
  • 격자의 크기가 N×N, 바이러스가 확산되는 동안 모든 칸을 최대 한 번 방문하므로 시간 복잡도는 O(N²)입니다.
  • 입력 최대 크기가 200×200이므로 충분히 효율적입니다.

---

결과

주어진 시간 S 후 특정 좌표 (X, Y)에 있는 바이러스의 번호를 정확히 출력합니다.

• 입력 예시:

  3 3  
  1 0 2  
  0 0 0  
  3 0 0  
  2 3 2

• 출력 예시:

  3

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!