[BOJ] 백준 1058 친구 - 파이썬

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

1058번: 친구

 

백준 1058문제이다. 

처음에는 이 문제가 Y의 영역 중에서 가장 큰 영역을 구하라는 것으로 착각하여 dfs로 풀었다가 오답처리되었다.

문제를 깊게 읽어보지 않은 탓이다.

문제를 조금 만 더 깊게 읽어보면 답을 구할 수 있다. 

 

문제를 잘 읽어보면 친구와의 관계에 대해 나온다. 즉 A와 친구이고, B와 친구인 C가 존재해야 한다. 라는 구문이 존재한다. 즉 한다리 건너뛰어서 친구인 사람이 있어야 된다는 소리다.

 

즉 흔히 K를 거쳐가는 경로를 구하는 플로이드와샬알고리즘이 떠올라야 한다. (안떠올라서 문제였지만... )

 

그리고 이후에 누가 가장 인싸인지, 그 수를 max로 걸러내주면 정답판정을 받을 수 있다. 

 

# 0943 
N = int(input())
v = [[0]*N for _ in range(N)]

def floyd():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                if g[i][j] == 'Y' or (g[i][k] == 'Y' and g[k][j] == 'Y'): 
                    v[i][j] = 1

g = []
for _ in range(N):
    g.append(list(input()))

floyd()

result = 0
for i in range(N):
    count = 0
    for j in range(N):
        if v[i][j] == 1:
            count += 1
    result = max(result, count)

print(result)