백준 1058번 - 친구

친구 문제 바로 가기

풀이 날짜: 2026-01-21

baekjoon 알고리즘 문제 풀이

풀이 코드

n = int(input())
friends = [list(input()) for _ in range(n)]

graph = [[0]*n for _ in range(n)]

for k in range(n):
    for a in range(n):
        for b in range(n):
            if a == b:
                continue
            if friends[a][b] == 'Y' or (friends[a][k] == 'Y' and friends[k][b] == 'Y'):
                graph[a][b] = 1

answer = 0
for i in graph:
    answer = max(answer, sum(i))
print(answer)
  

문제 접근

이 문제는 사람들 간의 친구 관계가 Y / N으로 주어지고, “친구이거나 친구의 친구(2-친구)”의 수를 세는 문제다. 문제를 읽자마자 사람 = 정점, 친구 관계 = 간선이라는 그래프 모델이 떠올랐다. 특히 “친구의 친구”라는 표현은 직접 연결(1단계) 뿐 아니라 한 번을 거쳐 도달할 수 있는 관계(2단계) 를 의미하므로 단순한 인접 확인이 아니라 경로 개념이 필요하다고 판단했다.

왜 이 문제가 ‘최단경로’ 문제인지

이 문제에서 중요한 건 “얼마나 멀리 있는지”가 아니라 최대 2단계 이내로 연결되어 있는지 여부다. 즉, 두 사람 A와 B 사이에

• 직접 친구면 거리 1
• 친구의 친구면 거리 2 이렇게 간선 수 기준의 거리 개념이 생기게 된다.

플로이드–워셜

“a가 k를 거쳐 b에 갈 수 있는가?”라는 플로이드의 핵심 아이디어

정답 계산

플로이드 갱신이 끝난 뒤, 각 사람 a에 대해 graph[a] 행의 합을 구하면 그 사람이 가진 2-친구 수가 된다. 그중 최댓값을 출력하면 문제에서 요구하는 답이 된다.