🖊️ 문제

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

---

🖊️ 풀이

일단, 컴퓨터들로 그래프를 만들고
그 그래프에 대해 DFS를 통해 바이러스에 연결된 애들을 찾는게 필요한 문제였다.

사실,, computers로 그래프 자료구조를 만들고 싶었는데,
입력받은 총 컴퓨터의 개수를 이용해서 동적할당해서 만들려고 했다.
그치만.. 주어진 최대 총 컴퓨터의 개수가 100개로 매우 작고, 굳이 순회할 필요는 없으므로
그냥 101개로 할당했다 (0번 인덱스는 사용하지 않을 예정임)

그래서 computers 그래프를
vector<int>의 배열로 만들었다.

이러한 상황에서, computers의 내부는

1 : 2, 5
2 : 1, 3, 5
3 : 2
4 : 7
5 : 1, 2, 6
6 : 5
7 : 4

이렇게 만들어줬다.
(computers[1]의 원소 : 2, 5라는 뜻)

그래서 그래프를 만들어줬고,
DFS만 해주면 된다.

전체 개수에 대해 방문여부(visited) 를 만들어줬고,
각 노드에 대해
아직 방문한 적이 없는 경우에 대해 재귀함수를 호출해줬다.
방문한 적이 있으면 다시 방문하지 않으므로
이 방문여부 체크 자체가 종료조건이 된다.

연결된 노드들에 대해 처음이자 마지막 방문 == 얘가 현재 컴퓨터와 연결되어 있음을 알려줌
-> answer++

그래서 각 노드들의 간선을 양방향으로 등록해줬지만,
방문한 노드들(visited[n] == true)에 대해서는 다시 방문(재귀함수 호출)하지 않는다.
그래서 종료조건이 유효하고, 마무리할 수 있다.

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

int answer = 0;
vector<int> computers[101];
bool visited[101]{ false };

void dfs(int n)
{
	visited[n] = true;
	for (int i = 0; i < computers[n].size(); i++) {
		int curCom = computers[n][i];
		if (visited[curCom] == false) {
			dfs(computers[n][i]);
			answer++;
		}
	}
}

int main()
{
	int computerCnt = 0;
	int pairNum = 0;
	cin >> computerCnt >> pairNum;

	int num1, num2;
	for (int i = 0; i < pairNum; i++) {
		cin >> num1 >> num2;
		computers[num1].push_back(num2);
		computers[num2].push_back(num1);
	}

	dfs(1);
	cout << answer;
}

문제 자체는 쉬우나,
그래프를 구현하는게 처음이었다.
dfs 겁먹지말자 이제 ~~