[백준1058/실버2] 친구 - Python

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

 

2-친구가 가장 많을떄, 그 2-친구 수를 출력하는 문제였다.

(A와 B가 2-친구 되는 법 : A,B가 서로 친구이거나, 겹지인 C 존재)

 

그래서 브루트포스로 n번 사람의 2-친구 수를 전부 구해서 계산했다.

 

# 성공 코드

# 단순 그래프 탐색
# python 32412 KB 48 ms

N = int(input())
adjl = [input() for _ in range(N)]

def friend(a, b):
	
    # 서로 친구인 경우
    if adjl[a][b] == 'Y':
        return True
	
    # 겹지인이 존재할 경우
    for f in range(N):
        if f == a or f == b:
            continue
        if adjl[f][a] == 'Y' and adjl[f][b] == 'Y':
            return True

    return False

result = 0

for i in range(N):
    cnt = 0 # i의 2-친구 수
    
    for j in range(N):
        if i == j:
            continue
        if friend(i, j): # i와 j가 2-친구이면 cnt += 1
            cnt += 1

    result = max(result, cnt)

print(result)

 

 

풀고보니 플로이드-워셜 문제로 풀 수 있어서 시간복잡도는 커지겠지만 다시 한번 풀어봤다.

 

# 플로이드 워셜
# python 32412 KB 92 ms

N = int(input())
adjl = [input() for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]

# 친구 관계 (Y면 거리 1, 본인은 거리 0)
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif adjl[i][j] == 'Y':
            dist[i][j] = 1

# 플로이드-워셜
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 2-친구 수 계산
result = 0
for i in range(N):
	# 거리가 2 이하라면 2-친구 가능
    cnt = sum(1 for j in range(N) if i != j and dist[i][j] <= 2)
    result = max(result, cnt)

print(result)