[boj][c++] 1325 효율적인해킹

탭으로 작성 수정필요

1325 효율적인 해킹

오랜만에 연습문제로 bfs문제를 풀었다.

이 문제에 접근하기 위한 키포인트는 방향그래프와 visit 배열의 초기화이다.

• 처음 그래프를 입력받을 때 단방향그래프로 입력받는다.
• 해당 그래프의 각 노드를 bfs한다.
  • 매번 visit배열을 초기화하여 각 노드의 연결횟수를 구한다.

visit배열을 초기화하여 굳이 모든 노드를 확인하는 이유는 이 그래프가 방향그래프이기 때문이다. 시작지점에 따라 연결 가능한 노드의 수가 달라진다. 방향그래프의 특성만 머리로 그리면 쉽게 떠올릴 수 있다. visit배열을 초기화하기 위해 set_zero라는 함수를 만들었는데, 생각해보니 memset내장함수로 가능하다 ㅋㅋ ㅜ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int> graph[10001];
int visit[10001];
vector<pair<int,int>> ans;

int bfs(int n)
{
	int cnt;
	
	cnt = 0;
	queue<int> buf;
	visit[n] = true;
	buf.push(n);
	while (!buf.empty())
	{
		int a=buf.front();
		buf.pop();
		cnt++;
		for(int i=0;i<graph[a].size();i++)
		{
			int k = graph[a][i];
			if(visit[k]==false)
			{
				buf.push(k);
				visit[k] = true;
			}
		}
	}
	return (cnt);
}

void set_zero(void)
{
	for(int i=1;i<=n;i++)
		visit[i]=0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		graph[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		ans.push_back({i,bfs(i)});
		set_zero();
	}
	int max_ans = -1;
	int index;
	for(int i=0;i<ans.size();i++)
	{
		if(ans[i].second > max_ans)
			max_ans=ans[i].second;
	}
	for(int i=0;i<ans.size();i++)
	{
		if(ans[i].second == max_ans)
			cout<<ans[i].first<<" ";
	}
}

후드집업 선물받았다ㅎㅎ