[백준/1058/파이썬] 친구

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

1058번: 친구

Problem

• 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 
• 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

조건

• 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다.
• 첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

SOL

문제를 잘 해석해야하는 문제이다. (당연한 소리 아닌가!?)

 

여기서 "2-친구"의 의미는 한 노드에서 edge가 2인 친구의 수를 의미한다.  몇개의 예시를 그려보면, 쉽게 이해가 될거다. BFS/DFS 뭘로 풀어도 상관은 없지만, edge의 수가 좀 더 중요한 DFS로 구현을 했다.

 

구현은 DFS로 했고, 인접행렬 자체를 DFS로 탐색하는건 오랜만이라서 좀 헷갈렸지만, 기억을 더듬어 가면서 구현을 했다.

 

# 친구
# depth 가 "2"인 노드까지 방문했을 때, 제일 많이 방문할 수 있는 노드를 찾는문제
# 인접행렬으로 나타난 걸 , DFS(재귀,스택)
import sys
input= sys.stdin.readline

N=int(input().rstrip())
board=[list(map(str,input().rstrip())) for _ in range(N)]

def dfs(idx):
    visited=[False for _ in range(N)]
    visited[idx] = True
    stk=[(idx,0)]
    cnt = -1
    
    while stk:
        cu_x,depth=stk.pop()
        for x in range(N):
            if board[cu_x][x]=="Y" and not visited[x]:
                if depth<2:
                    visited[x] = True
                    stk.append((x,depth+1))
        cnt+=1
    return cnt
ans=-1
for x in range(N):
    friend= dfs(x)
    ans=max(ans,friend)

print(ans)