6118_숨바꼭질

처음에 아래와 같이 풀었는데 메모리 초과 발생.

아무래도 2차원 배열에 의해서 메모리 초과가 발생한 것 같다.

int형 약 4억 개면 1.6GB 정도 되는데 문제 조건에서는 메모리가 256MB로 제한되어 있다.

 

#include <iostream>
#include <queue>

using namespace std;

int N,M;
int map[20002][20002]={0,};
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start][end]=1;
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int i=2;i<N+1;i++){
            
            if(dis[i]!= 0) continue;
            if(map[start][i]){
                dis[i] = dis[start]+1;
                q.push(i);
            }
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}

따라서 크기가 고정된 배열 대신 메모리를 동적으로 할당하는 벡터를 사용하였다.

 

2차원 배열 대신 벡터를 사용하니 메모리 초과가 발생하지 않았다.

 

 

#include <iostream>
#include <queue>

using namespace std;

int N,M;
vector <int> map[20001];
int dis[20002]={0,};

int main(void)
{
    queue <int> q;
    int start,end;

    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> start >> end;
        map[start].push_back(end);
        map[end].push_back(start);
        
    }
    
    q.push(1);
    dis[1] = 0;
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        
        for(int j=0 ; j<map[start].size();j++){
            if(dis[map[start][j]]!= 0 || map[start][j]== 1) continue;
            dis[map[start][j]] = dis[start]+1;
            q.push(map[start][j]);
            
        }
    }
    
    int MAX=0;
    int idx =0;
    int cnt =0;
    
    for(int i=1;i<N+1;i++){
        if(MAX < dis[i]){
            cnt =0;
            MAX = dis[i];
            idx = i;
        }
        if(MAX == dis[i])    cnt++;
    }
    
    cout << idx << " " << dis[idx] << " " << cnt;
    
    return 0;
}