[백준 1058/C++] 친구

1. 문제 / 난이도 : SilverⅡ

www.acmicpc.net/problem/1058

1058번: 친구

---

2. 풀이 및 코드 설명

직접 친구이거나, 한 다리 건너서 아는 사람이면 전부 세는 문제. 친구관계를 먼저 설정한 후에 직접 친구인 사람들을 먼저 세고 그 사람들의 친구인 사람들까지 세서 카운트했다.

나랑 직접 친구이고, 한 다리 건너서 하는 친구 일 수도 있기 때문에 중복을 없애기 위해 set을 사용하기로 했다. 그냥 set은 자동으로 정렬이 되지만, 해당 문제는 정렬까지는 필요없고 중복이 없기만 하면 되기 때문에 unordered_set을 사용했다. 

(1) 초기화 및 설정

char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

• map[i] : i와 친구인 사람들

(2) unordered_set 사용해서 친구 세기

unordered_set<int> friends; // 직접 친구 + 한 다리 건너서 아는 사람
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele); //직접 친구인 사람 추가
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f); // 그 사람과 친구인 사람 추가
			}
		}
		friends_cnt.push_back(friends.size()); 
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end()); // 카운트 정렬 
	cout << friends_cnt[N-1];

• friends : 직접 친구와 한 다리 건너서 아는 사람을 저장하는 set.
• friends_cnt : friends를 다 판별하고 난 뒤, 해당 set의 크기를 저장(set의 크기 = 아는 사람 수)
• 정렬 후 마지막 원소를 출력함으로써 제일 아는 사람이 많은 사람의 지인 수를 출력

---

3. 전체 코드

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<int> map[50];
vector<int> friends_cnt;
int N;

int main() {
	cin >> N;
	char temp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp;
			if (temp == 'Y') {
				map[i].push_back(j);
			}
		}
	}

	unordered_set<int> friends;
	for (int i = 0; i < N; i++) {
		for (auto &ele : map[i]) {
			friends.insert(ele);
			for (auto &f : map[ele]) {
				if (f != i) friends.insert(f);
			}
		}
		friends_cnt.push_back(friends.size());
		friends.clear();
	}

	sort(friends_cnt.begin(), friends_cnt.end());
	cout << friends_cnt[N-1];
}