[C++]백준 3182번 한동이는 공부가 하기 싫어!

📌문제 링크

---

https://www.acmicpc.net/problem/3182

📌문제 설명

---

그래프의 크기가 굉장히 작기 때문에 완전탐색을 돌릴 수 있다. 필자는 bfs로 가장 멀리 연결되어 있는 사람을 찾아 출력했다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
bool visited[1001];
int N, answerIdx, answerCnt, ls[1001];

void input(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> ls[i];
    }
}

void bfs(int idx){
    fill(visited, visited + 1001, false);
    queue<pair<int, int>> q;
    q.push({idx, 0});
    visited[idx] = true;
    int temp = 0;
    while(!q.empty()){
        auto [idx, cnt] = q.front();
        q.pop();
        temp = max(temp, cnt);
        if(!visited[ls[idx]]){
            visited[ls[idx]] = true;
            q.push({ls[idx], cnt + 1});
        }
    }
    if(temp > answerCnt){
        answerIdx = idx;
        answerCnt = temp;
    }
}

void solve(){
    input();
    for(int i = 1; i <= N; i++){
        bfs(i);
    }
    cout << answerIdx;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}