[C++] 백준 1325 효율적인 해킹 BFS, DFS

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define MAX_COM 10001

using namespace std;

vector<int> node[MAX_COM];
bool visited[MAX_COM];
vector<pair<int,int>> counts;

int BFS(int curr);
bool Sorted(pair<int, int> x, pair<int, int> y);

int main()
{
	ios::sync_with_stdio(false);

	int N, M, maxCounts = 0;

	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int temp[2];

		cin >> temp[0] >> temp[1];

		node[temp[1]].push_back(temp[0]);	//단방향 리스트를 사용한다.
	}

	for (int i = 1; i <= N; i++)
	{
		memset(visited, NULL, sizeof(visited));	//한번 순회할때마다 방문기록을 초기화한다.
		counts.push_back({ BFS(i), i });	//최대 해킹가능한 횟수를 기록한다.
	}

	sort(counts.rbegin(), counts.rend(), Sorted);	//최대값이 큰 순으로 정렬하며 컴퓨터번호가 앞번호인 순으로 정렬.

	for (int i = 0; i < N; i++)
	{
		if (maxCounts < counts[i].first)	//max보다 크면 출력
		{
			maxCounts = counts[i].first;
			cout << counts[i].second << " ";
		}
		else if (maxCounts == counts[i].first)	//그 뒤로 나오는 수들이 max와 같을 경우 출력
		{
			cout << counts[i].second << " ";
		}
	}
}

int BFS(int curr)
{
	int tempCount = 1;
	queue<int> q;
	q.push(curr);
	visited[curr] = true;
	
	while (!q.empty())
	{
		int currNode = q.front();
		q.pop();

		for (int i = 0; i < node[currNode].size(); i++)
		{
			int nextNode = node[currNode][i];

			if (visited[nextNode] == false)
			{
				tempCount++;
				q.push(nextNode);
				visited[nextNode] = true;
			}
		}
	}
	
	return tempCount;
}

bool Sorted(pair<int, int> x, pair<int, int> y)
{
	if (x.first < y.first)	//크면 무조건 앞순서로
	{
		return true;
	}
	else if (x.first == y.first)	//큰 것과 같다면 컴퓨터 번호를 오름 차순으로 정렬
	{
		return x.second > y.second;
	}
	else
		return false;	//나머지는 바꾸지않는다.
}

 

풀이

1. 단방향리스트로 받아온다.
2. BFS를 사용하여 더 빠르게 접근한다.
3. 해킹하는 방향이 오른쪽수가 왼쪽에 있는 수를 해킹한다. ( 반대방향으로는 해킹 불가 )
4. 해킹을 많이한 순서에서 컴퓨터 번호를 오름차순으로 정렬해준다.
5. 큰 순서대로 출력을 하는데 가장 큰 수를 출력한 뒤에 가장 큰 수와 값이 같다면 그 컴퓨터번호도 
   출력하도록 한다.

 

나름 빠르게 정답을 맞춘 것 같다.