View
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
문제 링크: https://www.acmicpc.net/problem/2606
【 풀이 】
DFS(깊이 우선 탐색)이나 BFS(너비 우선 탐색)을 이용하여 간단히 해결할 수 있다.
DFS가 조금 더 간단하게 구현 가능하기에 DFS를 이용하여 해결했다.
방문 여부를 나타내는 배열과 인접 리스트(각 점에 인접한 점들을 나타내는 배열)를 선언하고
인접 리스트 각 노드의 깊이를 우선으로 반복문으로 돌려보면서 방문 여부를 체크하면 된다.
【 코드 】
#include<iostream>
#include<vector>
using namespace std;
bool visited[101];
vector<int>graph[101];
void dfs(int x)
{
visited[x] = true;
for (int i = 0; i < graph[x].size(); i++)
{
int y = graph[x][i];
if (!visited[y])
dfs(y);
}
}
int main(void)
{
int cnt = 0;
int n, t;
cin >> n >> t;
for (int i = 1; i <= t; i++)
{
int num1, num2;
cin >> num1 >> num2;
graph[num1].push_back(num2);
graph[num2].push_back(num1);
}
dfs(1);
for (int i = 2; i <= n; i++)
{
if (visited[i])
cnt++;
}
cout << cnt;
}
728x90
'Problem Solving > Baekjoon' 카테고리의 다른 글
[백준] 9375번: 패션왕 신해빈 [C++] (0) | 2023.05.23 |
---|---|
[백준] 9095번: 1, 2, 3 더하기 [C++] (0) | 2023.05.22 |
[백준] 2579번: 계단 오르기 [C++] (0) | 2023.05.20 |
[백준] 1463번: 1로 만들기 [C++] (0) | 2023.05.19 |
[백준] 1003번: 피보나치 함수 [C++] (0) | 2023.05.18 |
reply