백준 6118 - 숨바꼭질(C++)

문제 링크입니다. https://www.acmicpc.net/problem/6118

6118번: 숨바꼭질

BFS를 이용해 푸는 문제입니다.

1번 정점에서 최대한 떨어진 곳과 거리를 구하는 문제입니다.

 

1번 정점에서 최소 길이로 다른 정점으로 가야하니 BFS를 사용해야 함을 알 수 있습니다.

저는 check 배열을 이용해, 다른 정점을 방문할 때마다 현재 정점의 값에서 1씩 더하는 방법으로 거리를 구했습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M;
vector<int> connect[20001];
int check[20001];
int dis, node, cnt;

void bfs(){
    queue<int> q;
    q.push(1);
    check[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] != 0) continue;
            check[xx] = check[x] + 1;
            q.push(xx);
        }
    }
    for(int i = 1; i <= N; i++){
        if(check[i] > dis){
            dis = check[i];
            node = i;
            cnt = 1;
        }
        else if(check[i] == dis) cnt++;
    }
}

void solve(){
    bfs();    
    cout << node << " " << dis - 1 << " " << cnt;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요