BaekJoon 1325 효율적인 해킹

Link : https://www.acmicpc.net/problem/1325

소스 결과 : 3444KB / 3188ms

출처 : BackJoon

 

설명

참 간단해 보이는데 생각보다 생각을 오래 한 문제

조건이 몇가지 존재 했다.

 

첫번째로는 N이 10000이기에 인접행렬을 사용하게 되면 10000 * 10000 * 4 byte를 사용. 메모리 초과가 나온다.

 

두번째로는 A가 B를 신뢰한다에서 단방향 그래프라는 것인데, B 가 A의 부모 정도로 생각하면 간단했다.

 

세번째로는 M이 100,000 이기에 Queue의 크기를 10만으로 잡은 원형 큐를 하나 사용했다.

 

 

첫번째 조건은 가변배열을 사용 해야만 하는 조건이었기에 평소와는 다르게 vector를 사용해서 해결했다.

 

알고리즘

1. A B를 입력받은 동시에 부모 자식관계를 나타내는 Vector에 추가

 

2. 1 ~ N 까지 반복

 

2-1. 현재 노드 i ( 최 상위 노드 ) 를 Queue 에 추가.

2-2. 탐색과 추가를 확인 하기 위한 배열 2개 생성

2-3. 현재 노드는 추가 한것으로 판정 처리

2-4. 자식 노드를 확인 하면서 BFS를 진행

 

3. 전체 노드중 최대값 식별

 

4. 최대값과 동일한 노드 번호 출력

 

사용 예제

5 4  3 1  3 2  4 3  5 3	1 2
15 10 4 7 4 8 4 9 7 1 8 1 9 1 11 10 12 10 13 10 14 10	1 10
7 7 1 2 2 3 3 1 4 5 5 6 6 7 5 7	7

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> childs[10001];
int childcount[10001];
int mqueue[100001];
int top = 0;
int bot = 0;

void push(int x)
{
	mqueue[top++%(100000)] = x;
}

int pop() {
	return mqueue[bot++% (100000)];
}

bool isempty() {
	return (top% (100000)) == (bot% (100000));
}

int main()
{
	int n, m;
	int max = 0;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		childs[b].push_back(a);
	}

	for (int i = 1; i < n + 1; i++)
	{
		push(i);

		bool check[10001]; // 탐색을 했는지 확인
		bool isadded[10001]; // 현재 노드가 이미 추가된 노드인지 확인

		fill_n(check, n + 1, false);
		fill_n(isadded, n + 1, false);

		isadded[i] = true; // 현재 노드는 추가한 것으로 판정

		while (!isempty())
		{
			int cur = pop();

			if (check[cur])
				continue;

			check[cur] = true; 

			for (int j = 0; j < childs[cur].size(); j++)
			{
				int idx = childs[cur][j];

				if (!isadded[idx])
				{
					push(idx);
					childcount[i]++;
					isadded[idx] = true;
				}
			}
		}
	}

	for (int i = 1; i < n +1; i++)
		if (max < childcount[i])
			max = childcount[i];

	for (int i = 1; i < n + 1; i++)
		if (max == childcount[i])
			cout << i << " ";

	return 0;
}