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';
}
Author And Source
이 문제에 관하여(172. 경쟁적 전염), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/172.-경쟁적-전염저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)