Computer Science & Engineering

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

이 문제는 BFS와 DFS모두 풀 수 있는 문제이다. 문제 알고리즘 분류는 깊이 우선 탐색이지만 글쓴이는 BFS를 이용하여 풀었다. 문제는 인접행렬이 주어졌을 때 2-친구의 수가 가장 많은 사람을 구하는 것이다. 2-친구는 두 사람이 친구이거나 한 사람을 건너서 친구인 친구를 말한다. 즉 깊이가 2 이하로 알고 있는 친구의 수이다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MN = 51;

vector<int> g[MN]; //인접 리스트
bool vst[MN]; //방문배열

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int rst = 0;
    int N; cin >> N;
    for(int i = 0; i < N; i++) {
        string s; cin >> s; //한 줄씩 string으로 입력 받음
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'Y') { //친구인 경우 인접리스트에 추가
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    for(int i = 0; i < N; i++) { //0번부터 N-1번까지 2-친구의 수 구하기
        queue<int> q; //BFS에 이용할 큐
        memset(vst, 0, sizeof(vst)); //방문배열 초기화
        vst[i] = true; //자기 자신 방문 체크
        int cnt = 0;
        for(int e : g[i]) { //자기 자신의 친구 체크
            if(!vst[e]) {
                vst[e] = 1;
                cnt++;
                q.push(e);
            }
        }
        while(!q.empty()) { //자기 자신의 친구의 친구들만 확인
            int now = q.front(); q.pop();
            for(int e : g[now]) {
                if(!vst[e]) { //친구가 아닌 경우. 즉 친구의 친구인 경우
                    vst[e] = 1;
                    cnt++;
                }
            }
        }
        rst = max(rst, cnt); //2-친구가 가장 많은 사람의 2-친구 수 갱신
    }
    cout << rst;
}

이 문제는 깊이를 확인할 필요 없이 깊이가 2까지만 탐색하면 되므로 0번부터 N-1번까지의 친구를 큐에 넣고 수를 세고 큐가 빌 때까지 그 친구들의 친구의 수만 세주면 된다. 이때 친구의 친구를 발견할 경우 큐에 넣지 않으면 깊이가 2인 친구까지만 탐색할 수 있다. 그렇게 구한 2-친구의 수의 최대값을 출력하면 간단히 답을 구할 수 있다.