백준 1058 친구

친구 또는 친구의 친구 수가 가장 많은 사람을 찾는 문제이다.

문제 풀이

 모든 사람의 친구들을 저장하기 위해 set 자료구조를 사용하였으며, key가 integer(사람의 번호), value가 set(친구들의 목록)인 딕셔너리를 사용하였다.

 1. N번째 줄에 N번째 사람과 친구인 사람들의 목록이 나오므로, N번째 줄에서 요소가 'Y'인 인덱스 M을 key가 N인 set에 넣는다. 또한, Undirected graph이므로 key가 M인 set에 N을 넣는 과정 역시 필요하다. (M은 N의 친구, N은 M의 친구)

 2. 또한 N의 친구들끼리도 서로 2-친구이다. N의 친구를 M1, M2라 하면, M1과 M2는 N을 매개로 한 2-친구가 된다. 따라서 key가 M1인 set에 M2를 넣고, 반대과정 역시 진행해 준다.

 3. 딕셔너리에서 value의 길이가 가장 큰 key를 반환한다.

Python Code

import sys
 
n=int(sys.stdin.readline())
dic = {}
for i in range(n):
    f_list = sys.stdin.readline()
    f_idx = [j for j in range(n) if f_list[j]=='Y']
    for f in f_idx:
        #직접친구
        if i in dic:
            temp = dic[i]
            temp.add(f)
        else :
            temp = set()
            temp.add(f)
        dic[i]=temp
        if f in dic:
            temp = dic[f]
            temp.add(i)
        else :
            temp = set()
            temp.add(i)
        dic[f]=temp
        # 친구의 친구
        f_set = dic[f]
        for f2 in f_idx:
            if f==f2: continue
            f_set.add(f2)
            if f2 in dic:
                temp = dic[f2]
                temp.add(f)
            else :
                temp = set()
                temp.add(f)
            dic[f2] = temp
ans = 0
for v in dic.values():
    if len(v)>ans:
        ans = len(v)
print(ans)

Line 10 ~ 12 : dic[N]에 M을 넣는 과정 (M은 N의 친구)

Line 17 ~ 22 : dic[M]에 N을 넣는 과정 (N은 M의 친구)

Line 29 ~ 35 : N의 친구들끼리 서로 친구로 넣어주는 과정

 

문제 링크

1058번: 친구