개발 지식/알고리즘
[백준] 1058 친구
트리맨스
2021. 5. 8. 01:11
반응형
문제를 잘 읽어보고 오자.
1058번: 친구
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람
www.acmicpc.net
이 문제도 평범한 그래프 탐색 문제이다. 주어진 사람들 중에 가장 많은 2-친구를 보유한 사람의 수를 출력하면 된다. 문제 읽어보면 복잡해 보이지만, 그냥 bfs로 탐색할 경우에 깊이가 2인 노드의 수를 체크하면 된다. 문제 분류에 플로이드-와샬 이라는 태그가 있는데, 사실 이거 뭔지 모르겠다. 몰라도 풀리긴 하는데, 나중에 한번 살펴봐야 할 듯 하다.
문제 풀이 구상을 간단히 해보자. Y의 위치에 대하여 a행 b열끼리 노드를 연결해 준다. 그 뒤에 모든 노드에 대하여 bfs를 돌린다. 이 때 queue에 push 할 때, 이전 노드의 깊이 정보를 넘겨주는 것이 필요하다. 다른 분들은 make_pair를 이용하여 vector의 입력 변수에 정수 쌍을 넣지만, 나는 그거보다는 구조체를 하나 만들어서 사용한다. 나는 이러한 방식이 더 편했던 것으로 기억한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#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);
}
|
cs |
생각나는 대로 막 풀었더니 약간 복잡한 것 같아 보인다.
반응형