[BOJ] 1325 효율적인 해킹

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

Note

참 간단해 보이는데 생각보다 생각을 오래 한 문제
조건이 몇가지 존재 했다.

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

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

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

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

알고리즘

1. A B를 입력받은 동시에 부모 자식관계를 나타내는 Vector에 추가
2. 1 ~ N 까지 반복
   1. 현재 노드 i ( 최 상위 노드 ) 를 Queue 에 추가.
   2. 탐색과 추가를 확인 하기 위한 배열 2개 생성
   3. 현재 노드는 추가 한것으로 판정 처리
   4. 자식 노드를 확인 하면서 BFS를 진행
3. 전체 노드중 최대값 식별 
4. 최대값과 동일한 노드 번호 출력

소스코드

#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;
}

2018-12-31 16:02:18에 Tistory에서 작성되었습니다.