백준 알고리즘 1325번 - 효율적인 해킹

dfs로 푸는 문제

노드를 하나씩 돌면서, 각각의 노드가 갈 수 있는 최대 횟수를 벡터에 저장한다.

처음에는 배열로 만들었지만, 최대 크기가 10000*10000이나 되서, 연결 여부를 배열로 만들면 시간 초과가 나온다.

 

또, 방문 여부를 판단하는 배열을 한 번씩 돌 때마다 초기화 시켜주어야 한다. 처음에는 초기화 시켜주지 않았지만, 최대길이가 짧은 노드부터 방문하게 된다면 최대 방문 순위를 재대로 셀 수 없게 된다.

 

풀이 과정

 

1. vector 배열을 만들어, from을 index로, to를 vector 배열에 push 한다.

2. 연결된 두 쌍을 찾아, dfs를 돌린다. 그 후 진행하는 횟수를 arr배열에 저장한다.

3. 오름차순 정렬이므로, arr배열에서 max값을 찾아 그와 동일한 값을 갖는 배열값을 1부터 배열 크기만큼 돌린다. 자동으로 정렬이 이뤄짐을 알 수 있다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n,m;
vector<int> graph[10001];
vector<int> visited;
vector<int> counts;
 
int ans=0; 

void dfs(int node){
    
    counts[node]++;
    ans=max(ans,counts[node]);
    
    int big=graph[node].size();
    for(int i=0;i<big;i++){
        
        int next=graph[node][i];
        if(!visited[next]){
            visited[next]=true;
            dfs(next);
        }
    }
}
int main(){
    
    scanf("%d %d",&n,&m);
    
    for(int i=0;i<m;i++){
        
    	int s,e;
        scanf("%d %d",&s,&e);
        graph[s].push_back(e);
    }
    
    counts=vector<int> (n+1,0);
    
    for(int i=1;i<=n;i++){
        visited=vector<int> (n+1,0); //방문 초기화
        
        visited[i]=true;
        dfs(i);
    }
    
    for(int i=1;i<=n;i++){
        if(counts[i]==ans){
            printf("%d ",i);
        }
    }
    return 0;
}