[백준] c++ 1058번 친구

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

1058번: 친구

1.문제 유형

- 브루투포스 알고리즘, 그래프 탐색, 그래프 이론 , 플로이드-워셜

2.문제 파악

2-친구가 가장 많은 사람을 구하는 문제이다. 

 

문제에서 제시한 2-친구의 설명이 모호한데

A와 C가 1-친구가 아니어도,

A와 B가 1-친구이고, B와 C가 1-친구라면 

A와 C는 2-친구이다. 라고 이해했다.

 

또한 문제에서 친구 관계를 "NYN"이런식으로 표현하고 있는데

첫번째 줄에 "NNY"라고 나와있다면

첫번째 사람의 1-친구는 3번째이다. 이렇게 이해했다. 

 

2-친구와 입력의 의미를 파악하는 것이 중요할 것 같다.

 

3.문제 풀이

플로이드-워셜로 푸는 방법도 있지만, DFS&BFS를 연습중이라 BFS로 풀었다.

이 문제는 DFS로 풀 수 없다고 한다(좀 더 이해 필요.)

 

해당 문제에서 그래프는 입력에서 제공하는 친구 관계이다. 

그래프를 입력 받은 후, 한 사람씩 2-친구를 검사하기 위해 BFS를 실행한다.

 

 

BFS에선 2-친구까지만 검사하면 되기 때문에 queue에 인덱스와 깊이 값을 한 쌍으로 사용한다.

 

추가적으로 2-친구 값은 1-친구와 2-친구의 합으로 계산해야 정답이 나왔다. 

 

4.코드 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N;
int f_max = 0;
char graph[50][50];
int visited[50];

//bfs: 넓은 탐색
void bfs(int x)
{
    fill_n(visited,50,0);
    
    //친구의 인덱스와 깊이
    queue<pair<int,int>> q;
    q.push({x,1});
    visited[x] = 1; 
    int f_cnt = 0;
    
    //사람 x의 2-친구 확인
    while(!q.empty())
    {
        int now_x = q.front().first;
        int depth = q.front().second;
        q.pop();
        if(depth>2) continue; //깊이 1~2만 검사
        for(int i=0;i<N;i++)
        {
            if(graph[now_x][i] == 'Y' && visited[i] == 0)
            {
                visited[i]=1;
                f_cnt++;
                q.push({i,depth+1}); //2-친구 검사를 위해 push
            }
        }
    }
    //cout<<"["<<x<<"]:"<<f_cnt<<"\n";
    if(f_cnt > f_max)
        f_max = f_cnt;
}

int main()
{
    cin>>N;
    
    
    
    for(int i=0;i<N;i++)
    {
         for(int j=0;j<N;j++)
        {
            cin>>graph[i][j]; //N-Y로 표현한 관계들
        }
    }
    //i 사람의 2-친구수 구하기
    for(int i=0;i<N;i++)
    {
        bfs(i);
    }
    cout<<f_max;
    return 0;
}