문제설명

• 친구의 관계를 입력으로 주어진다.
• 상근이는 1로 나타낸다.
• 친구의 친구까지만 초대가 가능하다(그래프에서 간선이 2개까지만 연결된)

문제풀이

• 문제를 보자마자 BFS로 풀어야 한다고 생각되었다.
• 문제는 BFS로 탐색문제만 풀어봤기 때문에 처음짠 코드는 연결되어있는 관계는 모조리 탐색해버린다..
• 구글링을 통해 간선의 길이를 어떻게 저장할 지 찾아보았다.

  -> 탐색했다는 visited리스트에 부모노드의 visited값 + 1 을 저장하는 것이다. 그리고 관계가 2를 넘는 즉, visited값이 상근이 1의 값 +2 를 초과하면 친구의 친구를 넘었다고 파악한다.

풀이 코드

n = int(input())
m = int(input())
arr = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  arr[x-1][y-1]=1
  arr[y-1][x-1]=1
visited = [0 for i in range(len(arr))]
from collections import deque
def bfs(start):
  dq = deque()
  dq.append(start)
  visited[start]=1
  while dq:
    top = dq.popleft()
    for i in range(len(arr)):
      if arr[top][i] ==1 and visited[i] ==0:
        visited[i] = visited[top]+1 # 부모의 visited값+1을 저장
        dq.append(i)
          
        
bfs(0)
answer = 0
for i in visited:
  if i>1 and i<4:
    answer+=1

print(answer)