그래프의 표현 - 효율적으로 해킹하기

이번 문제는 BFS와 DFS를 모두 이용할 수 있는 문제이다. 

 

<문제>

백준 - 1325: 효율적으로 해킹하기
https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다. 첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다.
 
예)
입력        출력
5 4         1 2
3 1
3 2
4 3
5 3
 

<문제 해결>

1. 문제에서 신뢰 관계라는 문제 접근 때문에 단방향 그래프로 입력 받아야 한다.

 

2. 각 노드를 방문할 때마다 그 노드와 연결된 모든 노드를 방문해야 한다. 이 과정을 노드 개수만큼 반복해야 한다.
 
3. 한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 출력하기 위해 각 노드를 방문할 때마다 이전 방문 기록을 초기화 해야 하며, 정답을 출력하는 벡터에 이전 노드 해킹 횟수 + 1을 해야 한다. 
 
4. DFS로 문제를 풀 때, 각 노드별 DFS를 크게 한 번 진행한 후 방문하지 않았던 노드가 있으면 DFS를 더 진행하는 코드를 main 함수에 추가해야 한다.
 

Corner case 정리)

가장 많이 해킹한 컴퓨터 횟수를 구할 때의 변수 설정(ex. max값을 인덱스가 아닌 가장 많이 해킹한 횟수로 설정해야 함)에 신경써야 함(예제 코드에서는 잘 작동하지만 정답 제출에서 실패하는 경우가 있음)
 

Approach 1. BFS - queue 이용

<슈도 코드>

n_num = 컴퓨터 개수(노드 개수)
e_num = 신뢰 관계 수(간선)
n1 = 노드1
n2 = 노드2

int main() {
	cin >> n_num >> e_num;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, 0);
	answer.resize(n_num + 1, 0);

	for (i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	for (i = 1; i <= n_num; i++) {
		fill(visited.begin(), visited.end(), 0); // 방문 기록 초기화
		BFS(i);
	}

	int max = answer[0];

	for (i = 1; i <= n_num; i++) {
		if (max < answer[i]) {
			max = answer[i];
		}
	}

	for (i = 1; i <= n_num; i++) {
		if (max == answer[i]) {
			cout << i << ' ';
		}
	}

}

void BFS(int n) {
	queue <int>	q;

	visited[n] = 1;
	q.push(n);
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (i = 0; i < graph[f].size(); i++) {
			if (visited[graph[f][i]] == 0) {
				visited[graph[f][i]] = 1;
				answer[graph[f][i]] += 1; // 노드 해킹 횟수 = 기존 노드 해킹 횟수 + 1
				q.push(graph[f][i]);
			}
		}
	}
}

 

<전체 코드>

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

void BFS(int n);
vector <vector <int>> graph;
vector <int> visited;
vector <int> answer;

int main() {
	int n_num, e_num;
	int n1, n2;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n_num >> e_num;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, 0);
	answer.resize(n_num + 1, 0);

	for (int i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	for (int i = 1; i <= n_num; i++) {
		fill(visited.begin(), visited.end(), 0); // 방문 기록 초기화
		BFS(i);
	}

	int max = answer[0];

	for (int i = 1; i <= n_num; i++) {
		if (max < answer[i]) {
			max = answer[i];
		}
	}

	for (int i = 1; i <= n_num; i++) {
		if (max == answer[i]) {
			cout << i << ' ';
		}
	}

}

void BFS(int n) {
	queue <int>	q;

	visited[n] = 1;
	q.push(n);
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (int i = 0; i < graph[f].size(); i++) {
			if (visited[graph[f][i]] == 0) {
				visited[graph[f][i]] = 1;
				answer[graph[f][i]] += 1;
				q.push(graph[f][i]);
			}
		}
	}
}

 

Approach 2. DFS - 재귀 함수 이용

<슈도 코드>

n_num = 컴퓨터 개수(노드 개수)
e_num = 신뢰 관계 수(간선)
n1 = 노드1
n2 = 노드2

int main() {

	cin >> n_num >> e_num;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, 0);
	answer.resize(n_num + 1, 0);

	for (int i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	for (int i = 1; i <= n_num; i++) {
		fill(visited.begin(), visited.end(), 0); // 방문 기록 초기화
		DFS(i);
		for (int j = 0; j < graph[i].size(); j++) { // 각 노드별 DFS를 크게 한 번 진행했을 때 방문하지 않았던 노드 모두 방문하기
			if (visited[graph[i][j]] == 0) {
				DFS(graph[i][j]);
				visited[graph[i][j]] = 1;
			}
		}
	}

	int max = answer[0];

	for (int i = 1; i <= n_num; i++) {
		if (max < answer[i]) {
			max = answer[i];
		}
	}

	for (int i = 1; i <= n_num; i++) {
		if (max == answer[i]) {
			cout << i << ' ';
		}
	}
}

void DFS(int n) {
	visited[n] = 1;
	
	for (int i = 0; i < graph[n].size(); i++) {
		if (visited[graph[n][i]] == 0) {
			visited[graph[n][i]] = 1;
			answer[graph[n][i]] += 1;
			DFS(graph[n][i]);
		}
	}
}

 

<전체 코드>

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

void DFS(int n);
vector <vector <int>> graph;
vector <int> visited;
vector <int> answer;
queue <int> q;

int main() {
	int n_num, e_num;
	int n1, n2;

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n_num >> e_num;

	graph.resize(n_num + 1);
	visited.resize(n_num + 1, 0);
	answer.resize(n_num + 1, 0);

	for (int i = 0; i < e_num; i++) {
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
	}

	for (int i = 1; i <= n_num; i++) {
		fill(visited.begin(), visited.end(), 0); // 방문 기록 초기화
		DFS(i);
		for (int j = 0; j < graph[i].size(); j++) {
			if (visited[graph[i][j]] == 0) {
				DFS(graph[i][j]);
				visited[graph[i][j]] = 1;
			}
		}
	}

	int max = answer[0];

	for (int i = 1; i <= n_num; i++) {
		if (max < answer[i]) {
			max = answer[i];
		}
	}

	for (int i = 1; i <= n_num; i++) {
		if (max == answer[i]) {
			cout << i << ' ';
		}
	}
}

void DFS(int n) {
	visited[n] = 1;
	
	for (int i = 0; i < graph[n].size(); i++) {
		if (visited[graph[n][i]] == 0) {
			visited[graph[n][i]] = 1;
			answer[graph[n][i]] += 1;
			DFS(graph[n][i]);
		}
	}
}