이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 37 번째 글 입니다.
목차
실버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를 적용하면서 연결된 선을 하나씩 늘려주면 된다. 시간 복잡도는 $O(NM)$ 이다.
나는 여기서 괜히 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;
}