처음으로 dfs문제 풀이 안 보고 완전히 내 힘으로 풀었다! 뿌듯하다. 오늘은 꼭 스스로 풀어봐야지 하는 마음가짐으로 손 댄 문제였는데 운이 좋았는지 스터디 준비하면서 풀었던 음료수 얼려 먹기라는 문제와 비슷했다. 로직은 그 문제에서 대부분의 영감을 얻었다.
정말 어렵게 느껴지는 부분도 역시 연습하다보면 풀리는구나 싶다. 그런데 조금 변형되면 다시 손대기 어려워질 것 같다. 이런식으로 며칠 막히는 파트는 꾸준히 연습문제를 풀어야겠다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> node[1001];
int visit[1001];
int n, m;
bool dfs(int num)
{
if (visit[num] == 0)
{
visit[num] = 1;
for (int i = 0; i < node[num].size(); i++)
dfs(node[num][i]);
return true;
}
return false;
}
int main()
{
int from, to, cnt;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> from >> to;
node[from].push_back(to);
node[to].push_back(from);
}
cnt = 0;
for (int i = 1; i <= n; i++)
{
if (dfs(i))
cnt++;
}
cout << cnt << "\n";
return 0;
}