문제 출처

1. 문제설명

  • N개의 컴퓨터가 있다.
  • A 컴퓨터가 B 컴퓨터를 신뢰하는 경우 B를 해킹하면,
    • A도 해킹할 수 있다는 의미이다.
  • 즉 A->B가 연결되었다는 의미로 해석된다.
    • A<->B가 아님!



2. 알고리즘 설계

  • 그래프 + 탐색 문제 이다.
  • 1번부터 돌면서 몇 개와 연결되어 있는지 탐색하면 된다.
  • 그러나, 한번 탐색한 노드는 다시 탐색하지 않아야 한다.



3. 로직

  • 값의 저장을 위해 2차원 벡터를 사용하였다.
  • 처음 그래프 간선을 저장할 때 각 2차원 배열에 1차원 벡터로 연결을 표시하였다.
  • 이후 DFS를 돌면서 연결된 노드 수를 세면 된다.
    • 이 때, 한 번 방문한 노드는 다시 갱신하지 않는다.
    • 한 노드의 탐색이 끝나면 {개수, 노드 번호}를 저장한다.
  • DFS를 탐색이 끝나면 {개수, 노드 번호} 벡터를 정렬한다.
    • 앞서 포스팅에서 언급했던 것처럼,
    • 개수를 앞에 넣어 저장하면 별도의 operator를 만들지 않아도 된다.
  • 개수가 같은 노드들을 출력한다.



4. 전체 코드

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int SZ = 10001;
vector<int> graph[SZ];
bool visited[SZ];
int n, m, cnt;


void dfs(int start) 
{
	cnt++;
	visited[start] = true;

	for (int i = 0; i < graph[start].size(); i++)
		if (!visited[graph[start][i]])
			dfs(graph[start][i]);
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;

	vector<pii> v;

	for (int i = 0; i < m; i++) {
		int to, from;
		cin >> to >> from;
		graph[from].push_back(to);
	}

	for (int i = 1; i <= n; i++) {
		dfs(i);
		v.push_back({ ~cnt,i });

		cnt = 0;
		memset(visited, false, sizeof(visited));
	}
	
	sort(v.begin(), v.end());

	cout << v[0].second << ' ';
	for (int i = 1; i < v.size(); i++)
		if (v[0].first == v[i].first)
			cout << v[i].second << ' ';

	return 0;
}

5. 소감

  • 시간 초과 때문에 굉장히 애먹었었다.
  • 한번 들린 곳을 안 들리게 만드는 게 관건인 문제였다.
  • 시간 제한이 별도로 없어도, 이렇게 구현하는 습관을 들여야겠다.