[백순코] 1325번 - 효율적인 해킹(14위)

flaxinger·2021년 7월 11일
0

개인적인 문제풀이 이후 타인의 코드를 참고했습니다.

문제 링크

Naive 풀이
다음은 백준 1325번 문제에 대한 naive 코드이다. 해당 문제는 그래프 탐색 문제로 BFS, DFS 모두 사용 가능하지만, BFS는 큐로 인해 메모리 사용량이 늘어나므로, DFS를 사용하였다. BFS, DFS가 가물가물하거나, 처음 보는 분이 있다면 나동빈님의 블로그(BFS, DFS)를 추천한다. 기본적인 풀이에 대하여 다음 블로그의 코드를 참고할 수 있다.

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>

using namespace std;

#define MAX 10001

int N, M;
vector <int> vec[MAX];
vector <int> check;
bool visit[MAX];
int cnt;

void DFS(int node_num) {
	visit[node_num] = true;

	for (int i = 0; i < vec[node_num].size(); i++) {
		int node_nextNum = vec[node_num][i];

		if (!visit[node_nextNum]) {
			cnt++;
			DFS(node_nextNum);
		}
	}
}

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
}

int main() {
	init();
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int Start_point, End_point;
		cin >> Start_point >> End_point;
		vec[End_point].push_back(Start_point);
	}
	
	int node_count = 0;

	for (int i = 1; i <= N; i++) {
		memset(visit, false, sizeof(visit));
		cnt = 0;
		
		DFS(i);
		if (node_count == cnt)
			check.push_back(i);

		else if (node_count < cnt) {
			node_count = cnt;
			check.clear();
			check.push_back(i);
		}
	}
	
	sort(check.begin(), check.end());
	for (int i = 0; i < check.size(); i++)
		cout << check[i] << " ";
	
	return 0;
}

이렇게 코드를 제출하면, 아래와 같이 약 3.3초의 시간이 걸리는 것을 확인할 수 있다. 그래프 문제고 최대 간선의 수가 100,000개, 최대 노드의 수가 10,000이기 때문에 백준 서버 상태에 따라 최대 4초까지 나오는 것을 확인하였다.

효율적인 코드

이렇게 큰 그래프를 다룰 때는, 그래프의 몇가지 성질만 알고 있어서도 시간을 굉장히 단축시킬 수 있다.

해당 문제는 방향 그래프로, 각 간선은 하나의 방향을 가진다. 이때 순환 그래프가 형성될 수 있는데, 순환

profile
부족해도 부지런히

0개의 댓글