백준 1058 : 친구

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

1058번: 친구

 

해결 방법 : DFS

• dfs를 쓰긴 했지만, 브루트포스, BFS, floyed-warshall 등 모두 가능할듯하다.
• target person으로 부터 2번 안에 도착할 수 있는 모든 사람들은 친구인점을 이용하면 된다.

import sys
input = sys.stdin.readline

def solution(N, arr):
    answer = 0
    friends = [set() for _ in range(N)] # 친구는 중복되지 않으므로 set을 사용

    def dfs(target, person, depth): # DFS (친구를 찾으려는 person, 현재 탐색할 person, 관계 depth)
        if depth == 3: # 깊이가 3인 친구는 2-friend가 아니다
            return

        for friend in range(N): # 현재 person의 친구 탐색
            if target != friend and arr[person][friend] == 'Y': 
                friends[target].add(friend)
                dfs(target, friend, depth + 1) 

    for t in range(N):
        dfs(t, t, 1)

    return max([len(f) for f in friends]) # 가장 많은 친구들 수

if __name__ == '__main__':
    N = int(input())
    arr = [input().strip() for _ in range(N)]
    result = solution(N, arr)
    print(result)