[BOJ] 1058. 친구 (python)

✏️ 문제

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

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

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

 

🤯 풀이 방법

이중 배열로 받아서 인덱스 탐색 하면 될 것 같아서 일단 YNN 형식으로 들어오는 값을 TF로 배열에 받았다.

이중 for문을 돌리면서 True면 바로 친구로 카운트하고 False이면 다른 인덱스들을 찾으면서 둘 모두를 친구로 갖고 있는 경우가 있는지 찾아서 다시 카운트에 추가

시간 초과 나올까 걱정했는데 다행히 패스!

 

import sys
input = sys.stdin.readline

N = int(input())    # 사람의 수 (<= 50)
L = [[] for _ in range(N)]
ans = 0

for i in range(N):
    str = input().rstrip()
    for s in str:
        if s == "Y":
            L[i].append(True)
        else:
            L[i].append(False)

for i in range(N):
    f = 0
    fl = []
    for j in range(N):
        if L[i][j] == True:
            f += 1
        elif i != j:
            for k in range(N):
            	# 둘 다를 친구로 갖고 있는 경우가 있는지 확인
                if L[i][k] == True and L[j][k] == True:
                    f += 1
                    break	# 안 하면 중복 체크

    ans = max(ans, f)


print(ans)

 

 

1058번: 친구