172. 경쟁적 전염

백준

1. BFS

from collections import deque

#시험관 크기, 바이러스 종류
n, k = map(int, input().split())

graph = [] 
data = [] #바이러스에 대한 정보 담는 곳

for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(n):
    #해당 위치에 바이러스가 존재하는 경우
    if graph[i][j] != 0:
      #바이러스 종류, 시간, 위치x, 위치 y 저장
      data.append((graph[i][j], 0, i, j) )

data.sort()
q = deque(data)

target_s, target_x, target_y = map(int, input().split())

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1 ]

while q:
  virus, s, x, y = q.popleft()

  if s == target_s:
    break
  
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if 0 <= nx < n and 0 <= ny < n:
      #아직 방문하지 않은 곳에 바이러스 넣기
      if graph[nx][ny] == 0:
        graph[nx][ny] = virus
        q.append((virus, s + 1, nx, ny))

print(graph[target_x - 1][target_y - 1])

2. C++

#include <bits/stdc++.h>

using namespace std;

class Virus {
public:
    int index;
    int second;
    int x;
    int y;
    Virus(int index, int second, int x, int y) {
        this->index = index;
        this->second = second;
        this->x = x;
        this->y = y;
    }
    // 정렬 기준은 '번호가 낮은 순서'
    bool operator <(Virus &other) {
        return this->index < other.index; 
    }
};

int n, k;
// 전체 보드 정보를 담는 배열
int graph[200][200];
// 바이러스에 대한 정보를 담는 리스트
vector<Virus> viruses;

// 바이러스가 퍼져나갈 수 있는 4가지의 위치
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int main(void) {
    cin >> n >> k;

    // 보드 정보를 한 줄 단위로 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            // 해당 위치에 바이러스가 존재하는 경우
            if (graph[i][j] != 0) {
                // (바이러스 종류, 시간, 위치 X, 위치 Y) 삽입
                viruses.push_back(Virus(graph[i][j], 0, i, j));
            }
        }
    }

    // 정렬 이후에 큐로 옮기기 (낮은 번호의 바이러스가 먼저 증식하므로)
    sort(viruses.begin(), viruses.end());
    queue<Virus> q;
    for (int i = 0; i < viruses.size(); i++) {
        q.push(viruses[i]);
    }

    int target_s, target_x, target_y;
    cin >> target_s >> target_x >> target_y;
    
    // 너비 우선 탐색(BFS) 진행
    while (!q.empty()) {
        Virus virus = q.front();
        q.pop();
        // 정확히 second만큼 초가 지나거나, 큐가 빌 때까지 반복
        if (virus.second == target_s) break;
        // 현재 노드에서 주변 4가지 위치를 각각 확인
        for (int i = 0; i < 4; i++) {
            int nx = virus.x + dx[i];
            int ny = virus.y + dy[i];
            // 해당 위치로 이동할 수 있는 경우
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                // 아직 방문하지 않은 위치라면, 그 위치에 바이러스 넣기
                if (graph[nx][ny] == 0) {
                    graph[nx][ny] = virus.index;
                    q.push(Virus(virus.index, virus.second + 1, nx, ny));
                }
            }
        }
    }

    cout << graph[target_x - 1][target_y - 1] << '\n';
}