글 읽기 - 그래프 고수님들은 필독!!!!

vjerksen 7년 전 0

해킹할 수 있는 방향대로 방향 그래프를 만들어준 후에, BFS를 이용해서 가장 많이 해킹할 수 있는 컴퓨터를 저장했습니다.

그리고 오름차순으로 정렬해서 출력하게 했고, Test case는 모두 맞았습니다. 다른 질문들의 Test case도 다 맞게 나오는데

어디서 문제인지 모르겠습니다. 도와주세요 고수님들

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<climits>
#include<map>
#include<set>
using namespace std;

int N,M;
vector<vector<int> > computer;
priority_queue<pair<int, int> > pq;
bool visit[10005];
int cnt[10005];
vector<int> ans;
void bfs(int s){
    int comp = -1;
    visit[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0;i<computer[cur].size();i++){
            int ncur = computer[cur][i];
            if(!visit[ncur]){
                q.push(ncur);
                visit[ncur] = true;
                cnt[ncur] = cur[cnt]+1;
            }
        }
    }
    for(int i=1;i<=N;i++){
        comp = max(comp,cnt[i]);
    }
    pq.push({comp,s});
}
int main(){
    cin >> N >> M;
    computer.resize(N+1);
    while(M--){
        int start,endd;
        cin >> endd >> start;
        computer[start].push_back(endd);
    }
    for(int i=1;i<=N;i++){
        memset(visit,false,sizeof(visit));
        memset(cnt,0,sizeof(cnt));
        bfs(i);
    }
    int temp_num = -1;
    while(!pq.empty()){
        int temp_val = pq.top().first;
        int temp_idx = pq.top().second;
        if(temp_num <= temp_val) {
            ans.push_back(temp_idx);
            temp_num = temp_val;
        }
        else
            break;
        pq.pop();
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

amok 7년 전 2

코드가 잘 이해가 안가는데, 그냥 단순히 "BFS를 이용해서" 라고 하지 말고, BFS를 어떻게 이용했는지 좀 자세히 적어주시면 좋을 것 같습니다.

amok 7년 전 2

읽어보니 각 노드마다 BFS를 수행하고, BFS트리의 높이(혹은 BFS의 시작 노드로부터 최단거리가 가장 먼 노드까지의 최단거리)를 구한 후, 그 높이가 가장 높은 정점을 출력하셨네요. 다음 반례를 참조하시기 바랍니다.

7 5
2 1
3 2
5 4
6 4
7 4

일단 제시하신 방법은 틀릴 뿐더러, 느립니다. BFS를 N번 수행해야 하기 때문입니다. BFS(혹은 DFS)를 노드의 개수만큼 수행하는 다른 방법이 있으나, 이 문제를 풀기는 너무 느립니다. 문제 분류가 DFS, BFS로 되어 있는데, 이 두 기본적인 탐색 알고리즘으로는 풀 수 없는 문제입니다. 풀어보진 않았지만 Strongly Connected Component 알고리즘으로 이 문제를 풀 수 있을 것 같습니다.

vjerksen 7년 전 1

to. amok

친절하고 성의있는 답변 감사합니다.

근데 왜 강결합요소를 사용해서 문제를 해결할 수 있다고 생각하시는지 알 수 있을까요?

강결합요소 내에 있는 노드들은 서로 간에 이동이 가능하다고 알고있는데 위의 반례에선 사이클이 형성되지 않습니다.

힌트 조금만 더 주시면 감사하겠습니다!

amok 7년 전 3

제가 제시한 반례에서는 사이클이 없기 때문에 강결합요소로 노드를 묶으나 그렇게 하지 않으나 차이가 없습니다. 오히려 강결합요소 찾기 알고리즘을 수행하는데 O(N+M)의 오버헤드가 추가로 들죠. 그러나 제가 제시한 반례가 가능한 입력의 전부가 아니므로, 입력으로 주어지는 그래프에 사이클이 있을지 없을지 알 수 없습니다. 사이클이 있는 그래프라면 하나의 강결합요소를 하나의 노드로 볼 수 있어서 탐색 시간이 줄어듭니다. 노드 1000개 정도를 하나로 볼 수 있다면 훨씬 빠르겠죠. 또한 강결합요소로 묶어줘서 사이클을 제거할 수 있습니다. 사이클이 없는 방향 그래프(DAG)는 훨씬 다루기 좋죠.

...... 라고 처음에 생각해서 강결합요소로 분해 후 풀이를 시도했으나, O(MN) 보다 빠른 풀이를 아무리 해도 생각해내지 못했습니다. DAG로 만들어봤자 소용없었습니다. 입력에 사이클이 있는 경우는 좀 줄였을지 모르나, 입력이 DAG인 경우는 전혀 줄인 것이 없는, 최악의 경우 theta(MN)인 단순한 알고리즘을 짜서 제출했습니다. 그런데 그렇게 했더니 맞았습니다.
개인적인 의견으로 이 문제 좀 이상한 것 같습니다. 정답 받은 다른 분들의 코드를 살펴봐도 다들 최악의 경우 theta(MN)입니다. M과 N이 크기가 저정도면 theta(MN)으로는 안 되는데... theta(MN) 보다 빠른 방법이 있긴 한 건가요? 아무튼 SCC로 분해해서 정답 판정을 받을 수 있는 것은 맞습니다.

vjerksen 7년 전 1

to. amok

답변 정말 감사합니다! 다른 분들한테 물어보니까 단순 BFS로 해결해도 time limit을 지킬 수 있다고 하더라고요.

이 기회에 강결합요소에 대해서 더 공부할 수 있었습니다. 다시 한번 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그래프 고수님들은 필독!!!!

vjerksen 7년 전 0

amok 7년 전 2

amok 7년 전 2

vjerksen 7년 전 1

amok 7년 전 3

vjerksen 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말