2024 - 08- 09 C++ 코딩테스트 10주완성 D+30

백준 1325 문제 - 효율적인 해킹

 

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다.

김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다.
둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다.
컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

 

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1. 변수 목록
//컴퓨터의 번호를 받을 정수형 변수 n
//컴퓨터 관계의 개수를 받을 m
//컴퓨터의 관계정보를 입력받을 1차원 정수 Vector a
//해킹수를 카운트할 정수형 변수 ret,max_ret
//신뢰관계 번호를 입력받을 정수형 변수 lt,rt
//해킹할 수 있는 카운트의 개수를 담은 1차원 정수 vector cnt
int n, m, max_ret,n_ret, lt, rt;
vector<int> a, cnt;

//2-4-3 bfs(int i) 함수
	//2-4-3-1 ret 을 1으로 초기화해준다.
	//2-4-3-2 if(a[a[i]] > 0 )
	//2-4-3-3 ret++
	//2-4-3-4 bfs(a[a[i]]);
int bfs(int i)
{
	int ret = 1;
	if (a[a[i]] > 0)
	{
		return ret + bfs(a[a[i]]);		
	}
	return ret;	
	// 1 - 3 - 4 - 5
	// 1 + 1 + 1 + 1 
}

int main()
{
	//2. 알고리즘
	//2-1 n과 m을 입력받는다.
	//2-2 0부터 n만큼 반복문
	//2-2-1 cnt[i] 안에 push_back(0) 을 해준다.
	//2-2-2 a[i] 안에 push_back(0) 을 해준다.
	//	  반복문 끝
	cin >> n >> m;

	for (int i = 0; i < n+1; i++)
	{
		cnt.push_back(0);
		a.push_back(0);
	}
	//2-3 0부터 m만큼 반복문
	//2-3-1 lt 와 rt 를 입력받는다.
	//2-3-2 a[rt] = lt 를 저장해준다.
	//	  반복문 끝
	for (int i = 0; i < m; i++)
	{
		cin >> lt >> rt;
		a[rt] = lt;
	}
	//2-4 0부터 a.size() 까지 반복문
	//2-4-1 만약 a[i] 가 1 이상일 경우
	//2-4-2 bfs(i) 호출
	//2-4-4 bfs 함수가 끝난뒤
	//2-4-4 max_ret 보다 ret 이 크면
	//2-4-5 max_ret 에 ret 값을 덮어씌운다.
	//2-4-6 cnt[i] = max_ret 을 해준다.
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] > 0)
		n_ret =	bfs(i);

		if (max_ret <= n_ret)
		{
			max_ret = n_ret;
			cnt[i] = max_ret;
		}		
	}
	
	for (int i = 0; i < n; i++)
	{
		if (max_ret == cnt[i])
			cout << i << " ";
	}

	//2-4-7 0 부터 n 까지 i++ 반복문
	//2-4-7-1 만약 max_ret 과 cnt[i]가 같다면 
	//2-4-7-2 cout << i << " "
	//		반복문끝
}

 

dfs 탐색으로 노드안의 값을 인덱스순서로 접근하고, 반복문이 돌때마다 ret++를 해주고

 

반복문이 끝나고 max_ret 과 비교하여 max_ret 에 ret의 최대수를 저장해준 다음에

 

동일한 최대수가 나올 경우 오름차순으로 반복문을 돌려 출력시켜주는 알고리즘을 짰었는데.. 

 

 

ㅜㅠ... 안된다.. 되게 간단한 거 같은데 잘 안풀린다. 디버깅을 돌려보니 ret에 대한 숫자가 맞아떨어지지 않는다..

 

아직 재귀함수에 대한 이해가 부족한 것 같다

 

강의실습코드를 보자!!

 

#include <bits/stdc++.h>
using namespace std;
 
vector<int> v[10001];
int dp[10001], mx, visited[10001], n, m, a, b;
 
int dfs(int here) {  
	visited[here] = 1;
	int ret = 1; 
	for(int there : v[here]){
		if(visited[there]) continue;
		ret += dfs(there); 
	} 
	return ret;
}
 
int main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> n >> m;  
	while (m--) {
     	cin >> a >> b;  
	    v[b].push_back(a);
	} 
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dp[i] = dfs(i); 
		mx = max(dp[i], mx);
	} 
	for (int i = 1; i <= n; i++) if (mx == dp[i]) cout << i << " "; 
	return 0;
}