[알고리즘][Python] 백준(BOJ) 1058 친구_파이썬

 

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

1058번: 친구

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 브루트포스 알고리즘, 깊이 우선 탐색

 

 

 

 

 

 

 

풀이 1

<내용>

• bfs를 이용해서 해결한다.
• 모든 친구를 for문으로 돌아 bfs로 2-친구의 수를 확인한다.

 

 

<코드>

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
friends = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    f = list(input().rstrip())
    for j in range(n):
        if f[j] == 'Y':
            friends[i][j] = 1

def bfs(n, i):
    check = [0] * n
    check[i] = 1
    que = deque([(i, 0)])
    count = 0
    while que:
        j, cnt = que.popleft()
        if cnt >= 2:
            continue
            
        for k in range(n):
            if not check[k] and friends[j][k]:
                count += 1
                check[k] = 1
                que.append((k, cnt+1))
                
    return count
        
res = 0
for i in range(n):
    res = max(res, bfs(n, i))
print(res)

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• Floyd-Warshall 알고리즘을 이용해서 해결한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
friends = [list(input().rstrip()) for _ in range(n)]
    
dp = [[0 for _ in range(n)] for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if friends[i][j] == 'Y' or (friends[i][k] == 'Y' and friends[k][j] == 'Y'):
                dp[i][j] = 1

res = 0
for row in dp:
    res = max(res, sum(row))
print(res)