실버2 : 그래프 문제이다.
생각
아.. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다. 그런데, N이 10000개 이고 M이 100000이기에 이 것을 배열로 무식하게 만들 수는 없고 vector를 사용하여 데이터를 저장해야 한다.
input
5 4
3 1
3 2
4 3
5 3
|컴퓨터|연결된|컴퓨터| |:-:------|:-:------|:-:------| |1|3|| |2|3|| |3|4|5| |4||| |5|||
이런식으로 모양을 맞춘 뒤에, 1번에 들어가서 연결된 컴퓨터를 따라 DFS를 적용하면서 연결된 선을 하나씩 늘려주면 된다. 시간 복잡도는 이다.
나는 여기서 괜히 1번을 탐색할 때, 3번을 탐색하게 되므로, 3번의 탐색 결과를 배열에 저장해 둔 뒤, 2번 컴퓨터를 탐색할 때 이 정보를 가져다가 사용했다. 하지만 어떠한 반례가 존재했고 계속 틀렸다..(하아)
아마 루프가 생기는 시점에 숫자가 다르게 적힐 것 같다는 생각이 든다. 그래서 그냥 무식하게 하면 된다. 무식한게 최고다 루프가 생길 수 있기 때문에 컴퓨터 한대를 탐색할 때 왔던 경로인지 체크해주는 배열이 필요하다.
Code
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> map;
int hack[10001] = {0};
bool checkVisit[10001] = {0};
int maxNumber = -1;
int ans = 0;
void go(int start){
checkVisit[start] = true;
int size = int(map[start].size());
if (size == 0) return;
for (int i = 0; i < size; i++) {
int nowNum = map[start][i];
if (!checkVisit[nowNum]) {
ans++;
go(nowNum);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i <= N; i++) {
vector<int> temp;
map.push_back(temp);
}
for (int i = 0; i < M; i++) {
int end, start;
cin >> end >> start;
map[start].push_back(end);
}
for (int i = 1; i <= N; i++) {
ans = 0;
fill(&checkVisit[0], &checkVisit[N+1], 0);
go(i);
hack[i] = ans;
maxNumber = max(maxNumber, ans);
}
for (int i = 1; i <= N; i++) {
if (hack[i] == maxNumber) cout << i << " ";
}
return 0;
}