문제 설명
https://www.acmicpc.net/problem/1325
A->B 라는 방향이 주어지는 그래프이며, 이 관계에서는 B가 A를 신뢰한다, B 입장에서 A를 해킹할 수 있다, 즉 B가 기준이 되는 문제이다. B 기준에서 연결된 노드의 개수가 몇 개인가, 노드별로 구분해서 카운트하고 정렬하는 문제이다. 방향 그래프 + 탐색 + 정렬 의 간단한 응용문제이나, 기계적으로 문제들을 풀었다면 사소한 부분들에서 헷갈리기 쉬운 문제이다.
문제풀이 시도 1
- 도착지점의 노드가 중요한 문제이므로, A B 라는 인풋이 주어졌을 때, A를 기준으로 graph를 그리지 않고, B를 기준으로 그래프를 그렸음(push_back을 거꾸로 했다는 의미)
- B 기준에서 연결된 노드의 개수를 세는 문제와 동일하다. B 기준에서 연결된 노드들의 개수를 세기위해, 본인은 단순히 연결된 노드들을 모조리 방문하고 카운트하는 방법으로 작성했다(이게 문제였음)
- 시간초과 및 효율성을 위해 본인은 아래 사진과 같이 반복되는 지점에 대한 해킹가능한 컴퓨터개수를 미리 계산해 덧셈하려고 하였음(이 경우, visited 했던 노드를 재 visit 하게 되는 경우가 발생하여 중복이 생기는 것을 해결할 수 없음)
발생한 문제점 및 고찰
- 시간복잡도를 고려하지 않았음: 그래프의 모든 인덱스에 대해 반복 + 해당 인덱스에서 연결된 모든 인덱스에 대해 방문 하는 구조로 작성하였으므로, 예상되는 시간 복잡도로는 100,000 * 100,000 = 10^10이므로, 시간초과가 날 수 밖에 없는 구조.
- 그래프탐색에 있어 효율적인 방안을 구상하지 않았음.
- 그래프에는 싸이클이 존재할 가능성이 매우 높고, 그렇다면 내 방식은 내부에서 반복문을 빠져나올 수 없게 됨. 해당 노드를 방문했는지의 여부를 파악하는 과정이 반드시 필요함.
- 해당 문제는 다른 그래프 탐색 문제들과는 다르게, 매 노드마다의 연결된 노드 개수를 세는 것이 핵심이므로, visited[cur_node]를 매번 초기화해주는 것이 핵심이었다.
- 본인은 반복을 피하기위해 visited를 초기화하지 않고, 해당 노드에 연결된 노드 개수를 저장해둔 뒤, 해당 노드 방문 시 그 값을 임의로 더하는 방식을 생각했으나, 위에서도 언급했지만 중복을 해결할 수 없었다. 다음과 같은 반례가 나왔다.
이러한 문제점들을 해결하기 위해, 매 노드 방문을 통한 전수조사 방식은 그대로 유지하되, 중복을 피하기 위해서 서치 시작 노드가 초기화될때마다 visited 배열을 초기화하는 방식으로 답안을 재 설계하였다.
작성코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;
int N, M, n, q;
vector<vector<int>> graph(10001);
int array_cnt[10001];
int cnt = 0;
int hack_max = INT_MIN;
bool visited[10001];
void DFS(int cur_node){
int next_node;
for(int i=0; i<graph[cur_node].size(); i++){
next_node = graph[cur_node][i];
if(!visited[next_node]){
cnt += 1;
visited[next_node] = true;
DFS(next_node);
}
}
return;
}
int main(){
cin >> N >> M;
for(int i=0; i<M; i++){
cin >> n >> q;
graph[q].push_back(n);
}
memset(array_cnt, 0, sizeof(int)*(N+1));
for(int l=1; l<=N; l++){
cnt = 0;
memset(visited, false, sizeof(bool)*(N+1));
visited[l] = true;
DFS(l);
array_cnt[l] = cnt;
hack_max = max(hack_max, array_cnt[l]);
}
for(int k=1; k<=N; k++){
if(array_cnt[k] == hack_max)
cout << k << " ";
}
cout << "\n";
/*
for(int m=1; m<=N; m++)
cout << array_cnt[m] << " ";
*/
return 0;
}