[백준] 효율적인 해킹(1325번)

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

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

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

입력

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

출력

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

예제 입력 1 복사

5 4 3 1 3 2 4 3 5 3

예제 출력 1 복사

1 2

---

1년 전쯤에 bfs로 풀었던 문제다.

dfs 실력을 테스트해보고싶어서 이번엔 dfs로 풀었다.

 

문제가 약간 헷갈렸는데, 양방향이 아닌 단방향 그래프였고 가장 많이 감염시킬 수 있는 컴퓨터의 번호를 구해야 했다.

1, 2번 컴퓨터가 3,4,5번 컴퓨터를 해킹할 수 있으므로 1, 2가 정답이었다.

즉 요지는 n번 컴퓨터에서 다른 컴퓨터를 몇 대나 방문할 수 있느냐였다.

따라서 n번 컴퓨터를 검사할 때마다 visit 배열을 초기화해서 몇 대를 방문할 수 있는지 세준다.

 

dfs를 실행하면 idx에 연결된 모든 컴퓨터를 검사하고 방문한 적 있는 컴퓨터는 건너뛰고, 새로 방문하면 cnt를 1 늘려준다. dfs로 idx에 연결된 모든 점을 방문하고 나오면 최대 몇 대의 컴퓨터를 방문했는지 검사해준다. 이번에 방문한 수가 최대라면 res를 갱신하고 result 벡터를 초기화해서 idx를 기록한다. 만약 최대값과 같다면 idx를 result 벡터에 기록한다.

 

bfs와 dfs로 푼 코드를 모두 올려놨다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9D%B8%20%ED%95%B4%ED%82%B9(1325%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

 

dfs 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> v[10001];
int visit[10001];
int res, cnt;
vector<int> result;
void dfs(int idx)
{
	visit[idx] = 1;
	for (int i = 0; i < v[idx].size(); i++) {
		int cur = v[idx][i];
		if (visit[cur]) continue;
		dfs(cur);
		cnt++;
	}
}


int main()
{
	cin >> N >> M;
	for (int a, b, i = 0; i < M; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		memset(visit, 0, sizeof(visit));
		cnt = 0;
		dfs(i);
		if (res < cnt) {
			result.clear();
			result.push_back(i);
			res = cnt;
		}
		else if (res == cnt) {
			result.push_back(i);
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";
}

 

 

bfs 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int p[10001];
vector<int> list[10001];
int N, M, res, idx;
void bfs(int t)
{
	queue<int> q;
	q.push(t);
	int visit[10001] = {};
	visit[t] = 1;
	int cnt = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < list[x].size(); i++) {
			if (visit[list[x][i]] == 0) {
				visit[list[x][i]] = 1;
				q.push(list[x][i]);
				cnt++;
			}
		}
	}
	if (res < cnt) {
		idx = 0;
		res = cnt;
		p[idx++] = t;
	}
	else if (res == cnt) {
		p[idx++] = t;
	}
}
int main()
{
	cin >> N >> M;
	int a, b;
	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		list[b].push_back(a);
	}
	for (int i = 1; i <= N; i++) 
		bfs(i);
	for (int i = 0; i < idx; i++) {
		cout << p[i] << " ";
	}
}