BOJ1068 python 그래프 S2

문제의 조건이 헷갈리게 써놨기 때문에 문제 조건을 이해하면 쉽게 맞출 수 있는 문제이다.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다. 이 지문에서 그래프는 대칭이다 라는 것을 알 수 있다. 인접행렬로 주어졌지만 친구를 찾는데 O(N)이라는 시간이 걸리기 때문에 그냥 행렬의 아랫 부분만 인접리스트로 다시 재구성했다.

친구인 조건이 이해하기 까다롭다
A와 B가 친구다. 는 쉽게 이해가 된다.
하지만 A와 B가 친구는 아니지만 A와 친구이고 B와 친구인 C가 있으면 2-친구라는 정의가 있다.
A-B-C 이렇게 만약에 있으면 A-C-B라는 말도 성립한다.
B는 누군가의 C일 수 있다는 점이다.
그러므로 A의 가중치 1~2인 친구들만 수를 더하면 2-친구의 수를 모두 구할 수 있다.

from collections import deque

N = int(input())

board = [list(input()) for _ in range(N)]
adj = [[] for _ in range(N+1)]
for i in range(N):
	for j in range(N):
		if i > j and board[i][j] == 'Y':
			adj[i+1].append(j+1)
			adj[j+1].append(i+1)

ans = [0 for _ in range(N+1)]
def bfs(start):

	Q = deque()
	Q.append(start)
	check[start] = True
    
	cnt = -1
	while Q:
		u = Q.popleft()
		if dist[u] > 2:
			continue
		cnt += 1
		for v in adj[u]:
			if check[v] == False:
				Q.append(v)
				check[v] = True
				dist[v] = dist[u] + 1
	ans[start] = cnt
	

for i in range(1, N+1):
	check = [False for _ in range(N+1)]
	dist = [0 for _ in range(N+1)]
	bfs(i)

print(max(ans))