악곱 == 악성곱슬

BFS

---

해당 문제를 bfs 로 생각한 이유는 다음과 같다.

• 친구,친구의 친구까지 결혼식에 초대한다 → 그래프 구조에서 depth가 2인 vertex까지 출력하면 되겠다
• input 이 두 vertex의 연결로 표현되었으니 linked list구조로 그래프를 구현하면 간단할 것 같다
• 친구 관계는 양방향이므로 bidirection으로 구현해야 한다.

코드는 아래와 같다. deque을 사용하였고, (vertex, depth) 구조로 queue를 운용하였다.

import sys
from collections import deque

def bfs(start, visited):
    queue = deque()
    depth = 0
    # 친구의 친구까지만 검색하기 위해 depth 변수를 추가하여 tuple 형식으로
    queue.append((start, depth))
    visited[start] = True

    while queue:
        vtx = queue.popleft()
        depth = vtx[1] + 1
        if depth > 2:
            break
        for v in linked_list[vtx[0]]:
            if visited[v] is True:
                continue
            queue.append((v, depth))
            visited[v] = True

    return visited.count(True) - 2

def solution(ll):
    visited = [False] * (N + 1)
    visited[0] = True
    answer = bfs(1, visited)
    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    M = int(sys.stdin.readline().rstrip())
    linked_list = [[] for _ in range(N+1)]
    for _ in range(M):   # 양방향
        se, ee = map(int, sys.stdin.readline().rstrip().split())
        linked_list[se].append(ee)
        linked_list[ee].append(se)
    print(solution(linked_list))