백준 1058번

풀이 1

친구 관계를 인접 리스트 형태로 저장했습니다.
예를 들어 보겠습니다.

A의 친구 : B, C
B의 친구 : A, D
C의 친구 : A, D

의 관계가 있을 때, A의 2-친구를 구하기 위해 t라는 리스트를 만듭니다. 이 리스트에는 두 종류의 원소들이 들어갑니다.

A의 친구들
A의 친구들의 친구들

현재 테스트 케이스를 기준으로 하면 t = ['B', 'C', 'A, 'D', 'A', 'D'] 가 됩니다.

여기서 set 자료구조를 통해 리스트 내의 중복을 제거합니다.

temp = set(temp)
temp = list(temp)

각 원소들마다 위의 과정을 수행해 결과값 중 가장 큰 값을 구합니다.

#1058번 친구
import sys
import copy

n = int(sys.stdin.readline())
graph = [[] for i in range(n)]

for i in range(n):
  t = list(sys.stdin.readline().strip())
  for j in range(n):
    if t[j] == "Y":
      graph[i].append(j)

results = [0 for i in range(n)]
for i in range(n):
  temp = copy.deepcopy(graph[i])
  
  for j in graph[i]:
    temp.extend(copy.deepcopy(graph[j]))

  temp = set(temp)
  temp = list(temp)
  if i in temp:
    temp.remove(i)
  results[i] = len(temp)

print(max(results))

풀이 2

플로이드 워셜 로 해결합니다.

import sys

n = int(sys.stdin.readline())
graph = [[0] * n for _ in range(n)]
connected = [[0] * n for _ in range(n)]

# 그래프 구성
for i in range(n):
    line = sys.stdin.readline().strip()
    for j in range(n):
        if line[j] == 'Y':
            graph[i][j] = 1

# 플로이드-와샬 알고리즘 수행
for k in range(n):
    for i in range(n):
        for j in range(n):
          if i==j:
            continue
          if graph[i][j] == 1 or (graph[i][k] == 1 and graph[k][j] == 1):
            connected[i][j] = 1
            

# 2-친구의 수 계산
max_friends = 0
for i in connected:
  max_friends = max(max_friends, sum(i))

print(max_friends)

백준 1058번 - 친구

SERIES: Baekjoon (18)

풀이 1

풀이 2