[ BOJ 백준 6118번 - 숨바꼭질 ] 해설 및 코드

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

 

목적

다음 그림과 같은 그래프에서 1번 정점과 다른 정점들과의 최단 거리를 구한 뒤, 그 중에서 가장 긴 길이의 정점에 관한 정보를 구하자.

접근법

1. bfs알고리즘을 이용하여 이전에 갱신한 거리보다 작은 경우 거리를 갱신하며, 이를 더이상 갱신할 것이 없을 때까지 반복한다. ( 백준 8061 - Bitmap문제와 유사한 방식을 이용한다.)

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
const int LEN=20001;
 
int n,s[LEN];
vector<int> path[LEN];
 
void calc(){
    queue<int> q; q.push(1);
    s[1]=0; f(i,2,n)s[i]=LEN;
    while(!q.empty()){
        int a=q.front(),dist=s[a]+1;q.pop();
        for(int& b:path[a])if(s[b]>dist)s[b]=dist,q.push(b);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int m;
    cin>>n>>m;
    ++n;
    while(m--){
        int a,b;cin>>a>>b;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    
    calc();
    
    int i=max_element(s, s+n)-s;
    cout<<i<<' '<<s[i]<<' '<<count(s, s+n, s[i]);
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.