[DFS] 백준 1325 효율적인 해킹

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

수행기간 : 2시간

 

실버 1의 난이도의 1325문제였다. 처음에 bfs를 통해 문제해결을 하려다가 생각하기에 더 복잡할 것 같아서 바로 dfs로 선회하여 문제를 해결하였다. 처음에 메모리 초과가 떴었는데, 그 이유는 map배열을 10000X10000으로 선언을 하다보니 메모리에서 에러가 떴었던 것 같다. 인접행렬을 이용한 문제풀이를 위주로 하다보니 인접 리스트로 접근하기가 쉽지 않았다. 그래도 구글링과 친구들의 도움을 받아 인접 리스트를 익히고 vector로 solving 결과 다행히 무난한 시간 3.5s 와 메모리를 사용하여 구현하였다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n, m;
bool visit[10001];
vector <int> map[10001];
int cnt[10001];
int ans = 0;
int maximum;

void dfs(int v) {
	ans++;
	visit[v] = true;
	for (int i = 0; i < map[v].size();i++) {
		int nv = map[v][i];
		if (!visit[nv]) {
			dfs(nv);
		}
	}
}
void init() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
}

int main() {
	init();
	cin >> n >> m;
	int a, b;
	for (int i = 0;i < m;i++) {
		cin >> a >> b;
		map[b].push_back(a);
	}
	for (int i = 1; i <= n;i++) {
		ans = 0;
		memset(visit, 0, sizeof(visit)); //이걸 빼먹엇엇음,,,,
		dfs(i);
		cnt[i] = ans;

		if (maximum < ans) {
			maximum = ans;
		}
	}
	for (int i = 1;i <= n;i++) {
		if (cnt[i] == maximum) {
			cout << i << " ";
		}
	}
}

++ 조만간 문제풀면서 익힌 인접리스트 dfs&bfs 글을 정리하여 쓸 생각이다.