이딴게 초등학생 문제?

시작

이 문제는 DFS/BFS와 관련된 문제인것 같다. 그 말은 즉 그래프 이론을 이용하면 편히 풀수 있다는 것을 알 수 있다. 그렇다면 한번 알아보자.
우선 n을 입력을 받는다, 그 후 m을 입력 받은 후 m개 만큼 연결된 컴퓨터를 입력 받으면 된다.
그렇다면 생각했을때, 자료를 어떻게 저장을 해야되는지 부터 생각을 해야된다. 우선 연결된 컴퓨터를 어떻게 확인을 할까? 생각을 해보면, 배열에다가 저장을 하면 된다. 그렇다면 어떻게 저장하면 되는지 한번 알아보자

배열 저장 방법

우선 예제를 따라 7개의 2차원 배열이 있다고 하자

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

이러면 생성을 되는데 예제 입력에서 1 2, 2 3, 1 5, .... 이렇게 연결이 되어 있다고 되있다. 그렇다면 한번 그거에 맞게 입력을 시켜보자면, 1번과 2번이 연결 되었다는 의미로

arr[1][2] = 1
arr[2][1] = 1

이런식으로 저장을 시켜 연결이 되었다는 겻을 표현하면 된다. 그렇다면 연결이 되었다는 것을 모두 표현하게 된다면?

0번 0 0 0 0 0 0 0 0
1번 0 0 2 0 0 5 0 0
2번 0 1 0 3 0 5 0 0
3번 0 0 2 0 0 0 0 0
4번 0 0 0 0 0 0 0 0
5번 0 1 2 0 0 0 6 0
6번 0 0 0 0 0 5 0 0
7번 0 0 0 0 0 0 0 0

이런식으로 저장이 될텐데 이걸 재귀로 한번씩 방문을 하면 되는데, 가장 문제점은 방문하고 나서는 무조건 방문을 했다는 표시를 남겨줘야된다. 물론 여기서 알려준 방법이 아닌 다른 방법이 있다. 그건 내가 알려준 것대로 0을 가득 채우는 방법이 아닌, 필요한 부분만 넣어 채우는 방법이다. 그럼 한번 확인 해보자.

1번 2 5
2번 1 3 5
3번 2
4번 7
5번 1 2 6
6번 5
7번 4

이런식으로도 반례를 저장해서 사용이 가능하다. 그렇다면 한번 알고리즘을 짜보자

알고리즘

1. 방문을 했다고 확인
2. arr의 크기만큼 반복
3. 만약 i가 자신과 같다면 넘기기
4. 방문을 안했으며, 만약 index의 밸류가 0이 아니면 방문

코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

using namespace std;

int cnt = 0;
vector<vector<int>> arr;
vector<int> checkArr;

void check(int n) {
	checkArr[n] = 1;
	for (int i = 1; i < arr[n].size(); i++) {
		// 자기 자신은 방문 안함
		if (i == n) continue;
		// 만약 방문을 안한 인덱스일때
		if (checkArr[i] == 0 && arr[n][i] != 0) {
			// 감염 확인
			cnt++;
			// 방문 확인
			checkArr[i] = 1;
			// 들어가기
			check(i);
		}
	}
	
}

int main() {
	int n, m;
	cin >> n;
	arr.resize(n + 1);
	checkArr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		arr[i].resize(n + 1);
	}
	
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = b;
		arr[b][a] = a;
	}
	check(1);
	cout << cnt;

}