백준) 1058 - 친구 [파이썬3]

문제)

 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

 A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

 

입력)

 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

 

출력)

 첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

---

from sys import stdin; input=stdin.readline
N = int(input().strip())
friends = {idx:[] for idx in range(N)}

for i in range(N):
    relation = input().strip()
    for j, f in enumerate(relation):
        if f == 'Y': friends[i].append(j)

result = 0
for key in friends.keys():
    tmp = set(friends[key].copy())
    for v in friends[key]:
        tmp |= set(friends[v])
    result = max(result, len(set(tmp))-1)
print(result)

풀이 :

 우선 5 - 8 번줄을 통해 총 N명 (0 번 ~ N-1 번) 까지의 관계를 정리한다. 그 결과 friends라는 딕셔너리에는 n번째 사람과 친구인 사람들이 정리될 것이다.

 그 후에 11 - 15 번 줄을 통해 2-친구수를 구하면 된다. 이 때  n의 2-친구수를 구하는 공식은

n의 친구들의 친구들 전체의 집합 - 본인

이다.

 예를 들어 문제의 예제 4 번을 보자.

예제 4번을 정리하면 위와 같은 정보가 생긴다.

 위의 표를 참고하였을 때, 0번의 2-친구 수를 구해보자. 우선 0의 친구는 [4] 한명이다. 그리고 4번의 친구는 [0, 1, 2, 9] 총 4명이다. 이 둘의 집합은 [0, 1, 2, 4, 9]가 된다. 이 때 0의 2-친구 수를 구하는 것이므로 본인(0)은 제외한 수를 세어주면 된다. 그러므로 0의 2-친구 수는 4가 된다.

 이번에는 1의 2-친구 수를 구해보자. 1의 친구는 [4, 6, 7] 총 3명이 된다. [4]의 친구는 [0, 1, 2, 9], [6]의 친구는 [1, 7] 마지막으로 [7]의 친구는 [1, 6]이다. 이 들의 총 집합은 [0, 1, 2, 4, 6, 7, 9]가 되고 마찬가지로 본인(1)을 제외한 6명이 1의 2-친구 수가 된다.

 위의 과정을 N번 반복한 뒤 가장 큰 수가 해당 문제의 정답이 된다.