백준 1325번 효율적인 해킹(C++)

문제

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>


using namespace std;

int compu_num,n;
vector<int> compu[10001];
int result[10001];
int vis[10001];
int maxi;

int dfs(int a)
{
	vis[a] = 1;
	int ret = 1;
	for (int k : compu[a])
	{
		if (vis[k])
			continue;
		ret +=dfs(k);
	}
	return (ret);
}
int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> compu_num >> n;

	for (int i=0;i < n;i++)
	{
		int down,up;
		cin >> down>> up;
		compu[up].push_back(down);
	}

	for (int i=1;i <= compu_num;i++)
	{
		memset(vis, 0, sizeof(vis));
		result[i]= dfs(i);
		maxi = max(result[i],maxi);
	}

	for (int i = 0; i<=compu_num;i++)
	{
		if (maxi == result[i])
			cout << i << " ";
	}
}

문제 풀이의 흐름

• 일단 몇개의 컴퓨터가 있는지와 몇줄을 입력 받을지 입력을 받는다.

• down이 up을 신뢰한다.

• 즉 신뢰를 받고있는 컴퓨터들의 갯수를 각 컴퓨터가 가지고 있는다.

• 다음으로는 각 컴퓨터 1번부터 깊이 우선 탐색을 실행한다.

• 1번부터 밑으로 본인을 신뢰하고 있는 컴퓨터들을 쭉 봐서 숫자를 결과에 저장하고

• 그 결과중에 가장 큰 값을 저장한다.

• 그리고 마지막에 담아뒀던 각각 컴퓨터가 감염시킬수 있는 컴퓨터의 숫자만큼 출력을 하면 된다.

주의 할 점

이 문제는 단순하게 생각하고 직접 감염시키는 녀석들을 세면 되는데

이상한 식으로 접근하면 좀 꼬인다.

반성 및 고찰

아직 컴퓨터처럼 생각하는게 잘 안됐다.

스트레스를 받았지만 괜찮다.. 조급하지말자

실패코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <string.h>
int compu_num,n;

using namespace std;
//2차원 배열
// [컴퓨터 총 갯수][몇개가 들어가는지 배열]

typedef struct s_com
{
	// int id; //이건 몇번째 컴퓨터인지
	int	cnt;// 신뢰 컴퓨터 몇개인지
	vector<int> trust;
}t_com;
int arr[10001];
vector<int>result;
int maxi = -1;

int dfs(vector<t_com> & compu,int a)
{
	if (compu[a].cnt == 0)
	{
		return (1);
	}
	for (int j=0;j < compu[a].cnt;j++)
	{
		if (dfs(compu,compu[a].trust[j]))
		{
			arr[compu[a].trust[j]]++;
			if (arr[compu[a].trust[j]] > maxi)
			{
				if (!result.empty())
					result.clear();
				result.push_back(compu[a].trust[j]);
				maxi=arr[compu[a].trust[j]];
			}
			else if (arr[compu[a].trust[j]] == maxi)
			{
				// cout << i << ":" <<arr[i]<<"\n";
				result.push_back(compu[a].trust[j]);
			}

		}
	}
	return (0);
}
int main()
{
	ios:: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> compu_num >> n;
	vector<t_com>compu(compu_num+1);
	for(int i=1;i <= compu_num;i++)
	{
		compu[i].cnt = 0;
	}
	for (int i=0;i < n;i++)
	{
		int down,up;
		cin >> down>> up;
		compu[down].trust.push_back(up);
		compu[down].cnt++;
	}
	for (int i=1;i <=compu_num;i++)
	{
		sort(compu[i].trust.begin(),compu[i].trust.end());
		// for (int j=0;j<compu[i].cnt;j++)
		// {
		// 	cout << compu[i].trust[j] << " " ;
		// }
		// cout << "\n";
	}
	for (int i=1;i <= compu_num;i++)
	{
		dfs(compu,i);
	}

	for (auto it : result)
	{
		cout << it << " ";
	}
}

결과는 잘나오는데 시간 초과로 실패했다..

Uploaded by N2T