백준 1058 : 친구 ( Python )

문제 링크

📌 사용 알고리즘 : brute forcing

N 범위가 작기 때문에 브루트포스로 해결 가능합니다.

문제에서 주어지는 입력은 행렬 형식이고 i 번째 사람이 j 번째 사람과 친구가 되기 위해서
graph[i][j]==graph[j][i]=='Y' 이어야 합니다.

만약 그러한 경로가 없다면 임의의 다른 정점 k 를 선언하고
i 번째 사람과 k 번째 사람이 친구이고 j 번째 사람과 k 번째 사람이 친구이면 i 번째 사람과 j 번째 사람도 친구입니다.

이때 구하고자 하는것은 가장 유명한 사람의 2-친구의 수 이기 때문에
1부터 N 번째 사람중에 친구가 가장 많은 사람의 수를 출력하면 됩니다.

시간복잡도는 O(N^3) 입니다.

플로이드 워셜을 사용해서도 풀 수 있습니다.
i 에서 j 로 가는 경로가 둘다 Y 라면 가중치를 1 로 주고
모든 정점에서 다른 모든 정점으로 가는 최단거리가 2 이하이면 친구입니다.

📌 코드

import sys,math
input=sys.stdin.readline
from functools import lru_cache
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

N=I()
graph=[ list(input().rstrip()) for _ in range(N) ]
ans = 0

for i in range(N):
    visited = 0
    for j in range(N):
        if i==j: continue
        if graph[j][i] == 'Y' and graph[i][j] == 'Y':
            visited +=1
        else:
            for k in range(N):
                if i==k or j==k: continue
                if graph[i][k] == 'Y' and graph[j][k] == 'Y' and graph[k][i] == 'Y' and graph[k][j] == 'Y':
                    visited+=1
                    break # break를 안하면 중복이 발생할 수 있음.
    ans = max(ans , visited)

print(ans)