[백준/1058][Python] 친구

문제

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

1058번: 친구

풀이

문제 이해부터 하자면, 2-친구라고 말해서 좀 복잡한데 그냥 A-B가 친구이거나 / A-B가 친구가 아니여도 A, B에게 C라는 공통된 친구가 있으면 A-B가 친구가 된다. (A-C, B-C친구 -> A-B친구) 

이 문제에는 다양한 풀이법이 있다. 아무래도 n이 최대 50이라 완전탐색, O(n^3)에도 문제 해결이 가능하다.

• BFS :여기 정리가 잘 되어있는데 나는 잘 이해가 안된다ㅠ.ㅜ https://fre2-dom.tistory.com/159
• 플로이드-워셜: 사실 그냥 그래프로 풀었는데 찾아보니 플로이드랑 비슷

코드

n = int(input())
r = []
ans = [0]*n
for i in range(n):
  s = input()
  r.append(s)
#print(r)

for i in range(n):
  for j in range(n):
    if r[i][j] == 'Y': #Y인 경우 일단 ans에 값 카운팅
      ans[i] += 1
    elif i!=j: #친구가 아닌 경우 겹치는 친구가 있나 확인
      for k in range(n):
        if r[i][k] == 'Y' and r[j][k] == 'Y':
          ans[i] += 1
          break
print(max(ans))

회사 외부망엔 파워포인트가 없네...

표를 문자 그대로 저장한다.
그리고 0~4의 친구들을 각각 차례대로 확인해준다. 
만약 Y인게 있으면 바로 ans[0]의 값을 1 증가시켜준다. - (0,1)의 경우 Y이므로 바로 친구 수 증가
그런데 N이라면? 겹치는 친구가 있나 확인해줘야 한다. - (0,2)의 경우 N이므로 0의 친구, 2의 친구를 모두 확인해 겹치는 친구가 있는지 확인해준다. (0,1), (2,1)가 모두 Y이기 때문에 0과 2는 겹치는 친구 1이 존재한다.