[백준][1325번][BFS] 효율적인 해킹

효율적인 해킹

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

<코드>

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int main(void){
 
    int N, M;
    vector<int> a[10001];
    queue<int> que;
    int save[10001];
    int size = 0;
    int max = 0;
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++){
        int start, end;
        scanf("%d %d", &end, &start);
        a[start].push_back(end);
    }
 
    for (int i = 1; i <= N; i++){
        int count = 0;
        int visit[10001] = {};
        
        que.push(i);
        visit[i] = 1;
        count++;
 
        while (!que.empty()){
            int now = que.front();
            que.pop();
 
            for (int j = 0; j < a[now].size(); j++){
                int temp = a[now][j];
 
                if (visit[temp] == 0){
                    visit[temp] = 1;
                    que.push(temp);
                    count++;
                }
 
            }
        }
 
        if (max < count)
        {
            size = 0;
            max = count;
            save[size++] = i;
        }
        else if (max == count)
        {
            save[size++] = i;
        }
 
    }
 
    for (int i = 0; i < size; i++)
        printf("%d ", save[i]);
 
    return 0;
}

<문제 푼 요령>

 1. 처음 받아오는 값으로 인접 리스트를 만들어 관리한다. 

 2. 각 숫자에 대해서 BFS를 하면서 완전 탐색하여서 count를 올린다. 이 count값이 가장 높게 나오는 숫자를 찾는다.

 3. 여기서 각 숫자를 탐색하는 숫자는 오름차순으로 검색을 해서 max 값을 찾는것인데 만약 같은 경우가 있으면 이전에 찾은 값에 다음값에 저장을 해서 이전의 찾은 값도 보존해야 한다. 

 4. 정말 사소하지만 부등호를 넣고 안넣고를 조심하자 (이게 많은 문제를 일으킬 수 있다.)