취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11255번 문제인 ITAI Virus이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11255

조건에 따르면, (1)주어지는 바이러스 진원지 및 (2) 진원지와 직접적으로 인접한 도시들에 ITAI Virus가 퍼지게 됨을 알 수 있다.

각 도시와 연결된 도시가 어디인지를 인접행렬 또는 인접리스트의 형태로 저장하고 주어진 조건을 만족하는지 체크하는 배열을 활용하면 문제가 요구하는 값을 충분히 빠르게 계산할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N, M, K;
vector<int> G[1001];
int A[1001];

void solve() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) G[i].clear();
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	memset(A, 0, sizeof(A));
	while (K--) {
		int x; cin >> x;
		A[x] = 1;
		for (auto &y : G[x]) A[y] = 1;
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) ans += A[i];
	cout << ans << '\n';
}

int T;

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

	cin >> T;
	while (T--) solve();
}