[Python] 1058. 친구

https://www.acmicpc.net/problem/1058

1058번: 친구

 

접근법

• 플로이드 워셜을 통해 직접적인 친구 관계이거나 다른 한명을 건너 친구인 수를 모두 구함
• 그 중 maximum 값을 출력

def input_func():
    N = int(input())
    arr = []
    for i in range(N):
        # input.split()을 하지 않으면 한 글자씩 분리하여 저장
        arr.append(list(input()))
    return N, arr


def solution(N, arr):
    friend_num = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if j == k:
                    continue
                if arr[j][k] == 'Y' or (arr[j][i] == 'Y' and arr[i][k] == 'Y'):
                    friend_num[j][k] = 1

    ans = 0
    for row in friend_num:
        ans = max(ans, sum(row))
    print(ans)


def main():
    N, arr = input_func()
    solution(N, arr)
    return


if __name__ == '__main__':
    main()

---

 

사용된 알고리즘

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 플로이드-워셜