X Tutup
#include 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 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 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'; }
X Tutup