문제 링크: https://www.acmicpc.net/problem/3182

 

선배들의 지목 관계가 그래프로 나옵니다. 모든 노드부터 탐색을 시작해서 방문한 노드 수를 세서 업데이트 해주면 됩니다.

하나 이상의 정답이 있을 때 번호가 작은 선배를 출력해야 하는데, 번호가 작은 노드부터 탐색을 시도해보면 이 조건은 자연히 만족됩니다

#include <bits/stdc++.h>
using namespace std;


int next_person[1000];
bool visited[1000];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int to;
		cin >> to;
		--to;
		next_person[i] = to;
	}

	int meet=0;
	int min_idx=0;

	for (int i = 0; i < n; ++i) {
		memset(visited, 0, sizeof(visited));

		int current = i;
		int cnt = 0;
		while (!visited[current]) {
			visited[current] = true;
			current = next_person[current];
			++cnt;
		}

		if (cnt > meet) {
			meet = cnt;
			min_idx = i;
		}
	}

	cout << min_idx+1;
	
	return 0;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 1662: 압축  (0) 2020.08.01
[백준][C++] 5719: 거의 최단 경로  (0) 2020.08.01
[백준][C++] 3181: 줄임말 만들기  (0) 2020.07.31
[백준][C++] 3184: 양  (0) 2020.07.31
[백준][C++] 19539: 사과나무  (0) 2020.07.31