[Python] 1058 - 친구 (실버3)

1. 문제 설명

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

1058번: 친구

 

---

2. 아이디어

당시에 이 문제를 풀 아이디어를 떠올리지 못해서 구글링을 통해 찾아낸 방법이

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이었는데

애초에 다이나믹 알고리즘도 모르던 내가 이걸 100% 이해할 수 있었을리가 없다.

근데 난 왜 이걸로 문제를 풀어놨을까..? 분명한 건 구글링의 도움을 받아 문제를 풀었었다.

 

알고리즘에 대한 포스팅은 이후에 한 번에 정리하도록 하고 간략하게 설명하자면

다익스트라 알고리즘은 특정 노드에서 다른 노드로 이동하는 최단 거리를 찾는 방법이고,

플로이드-워셜도 최단 거리를 찾긴 하지만 시작 노드가 여러개라는 차이가 있다.

 

해당 알고리즘을 이해하면 끝나는 문제이기 때문에 이번 포스팅에서 풀이를 다루지는 않겠다.

 

---

3. 코드

def solution():
    n = int(input())
    friends = [list(input()) for _ in range(n)]
    famous = [[0]*n for _ in range(n)]
    answer = 0

    for k in range(n): # 경유점
        for row in range(n): # 출발점
            for col in range(n): # 종착점
                if row == col:
                    continue
                if friends[row][col] == 'Y' or (friends[row][k] == 'Y' and friends[k][col] == 'Y'):
                    famous[row][col] = 1
    for idx in famous:
        answer = max(answer, sum(idx))
    print(answer)

solution()