[백준] 1058 친구

 

 

문제를 잘 읽어보고 오자.

www.acmicpc.net/problem/1058

1058번: 친구

 

이 문제도 평범한 그래프 탐색 문제이다. 주어진 사람들 중에 가장 많은 2-친구를 보유한 사람의 수를 출력하면 된다. 문제 읽어보면 복잡해 보이지만, 그냥 bfs로 탐색할 경우에 깊이가 2인 노드의 수를 체크하면 된다. 문제 분류에 플로이드-와샬 이라는 태그가 있는데, 사실 이거 뭔지 모르겠다. 몰라도 풀리긴 하는데, 나중에 한번 살펴봐야 할 듯 하다.

 

문제 풀이 구상을 간단히 해보자. Y의 위치에 대하여 a행 b열끼리 노드를 연결해 준다. 그 뒤에 모든 노드에 대하여 bfs를 돌린다. 이 때 queue에 push 할 때, 이전 노드의 깊이 정보를 넘겨주는 것이 필요하다. 다른 분들은 make_pair를 이용하여 vector의 입력 변수에 정수 쌍을 넣지만, 나는 그거보다는 구조체를 하나 만들어서 사용한다. 나는 이러한 방식이 더 편했던 것으로 기억한다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
 
/*
bfs를 이용하여 구현했다.
깊이가 2가 되는 구간까지 탐색 후 방문한 지점에 대해서 계산함.
*/
 
typedef struct
{
    int data;
    int depth;
} loc;
 
vector<int> v[51];
 
int bfs(int start, int N)
{
    int ans = 0;
    int visited[51];
    queue<loc> q;
 
    memset(visited, 0, sizeof(visited));
    q.push({start, 0});
    visited[start] = 1;
    while (!q.empty())
    {
        int start = q.front().data;
        int depth = q.front().depth;
        if (depth >= 2)
            break;
        q.pop();
        /* 
        auto 연산자는 알아서 형태를 지정한다. 
        여기서는 std::iterator 이므로 포인터를 붙여야 실제 값이 나온다.
        */
        for (auto i = v[start].begin(); i != v[start].end(); i++)
        {
            /* 새로운 노드 발견 시 탐색 진행한다. */
            if (!visited[*i])
            {
                visited[*i] = 1;
                q.push({*i, depth + 1});
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        if (visited[i])
        {
            ans++;
        }
    }
    return (ans - 1);
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N, maxnum;
    string str;
    int arr[51];
 
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> str;
        for (int j = 0; j < N; j++)
        {
            if (str[j] == 'Y')
            {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    maxnum = 0;
    for (int i = 0; i < N; i++)
    {
        /* 깊이가 2인 노드의 개수, arr 인덱스에 저장한다. */
        arr[i] = bfs(i, N);
        maxnum = max(maxnum, arr[i]);
    }
    /* 최댓값에 해당하는 인덱스를 오름차순으로 출력한다. */
    for (int i = 0; i < N; i++)
    {
        if (maxnum == arr[i])
        {
            cout << arr[i];
            return (0);
        }
    }
    return (0);
}

 

생각나는 대로 막 풀었더니 약간 복잡한 것 같아 보인다.