백준 2606
https://www.acmicpc.net/problem/2606
풀이 전 나의 생각
컴퓨터 네트워크의 연결 구조가 그래프의 형태로 주어진다.
이때, 첫 번째 컴퓨터에 웜 바이러스가 퍼졌을 때 최대 몇 대의 컴퓨터 까지
퍼질 수 있는지 구해야 한다.
조건
- 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
과정
웜 바이러스는 무조건 1부터 시작하고, 컴퓨터 1번과 연결된 컴퓨터들을 탐색하려면
그래프의 형태로 값을 저장해놔야 한다.
다음으로 DFS를 이용하여 각 컴퓨터를 탐색한다.
컴퓨터가 방문 조건을 만족하며 탐색 됐다는 의미는 웜 바이러스에 걸렸다는 의미기 때문에,
방문 표시를 해주며 최종 결과값을 증가시켜준다.
1. 컴퓨터 네트워크의 구조를 저장한다.
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
link[u].push_back(v);
link[v].push_back(u);
}
2. DFS탐색으로 컴퓨터의 방문 표시를 해주며 웜 바이러스 현황을 체크해준다.
void dfs(int st)
{
visted[st] = true;
for (int next : link[st])
{
if (!visted[next])
{
dfs(next);
ans++;
}
}
}
풀이
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
using namespace std;
vector<vector<int>> link(101);
bool visted[101];
int ans = 0;
void dfs(int st)
{
visted[st] = true;
for (int next : link[st])
{
if (!visted[next])
{
dfs(next);
ans++;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
link[u].push_back(v);
link[v].push_back(u);
}
dfs(1);
cout << ans;
}
'알고리즘 및 자료구조 > 그래프' 카테고리의 다른 글
C++ 1325 효율적인 해킹 (0) | 2024.03.28 |
---|---|
C++ 백준 1389 케빈 베이컨의 6단계 법칙 (0) | 2024.03.27 |
C++ 백준 2660 회장뽑기 (0) | 2024.03.26 |
C++ 백준 11403 경로 찾기 (0) | 2024.03.25 |
C++ 백준 5567 결혼식 (0) | 2024.03.22 |