BOJ - 5567 - 1학년

Updated:

import sys
from collections import deque

def BFS(graph, N):
    visit = [False] * (N + 1)
    dq = deque()
    dq.append((1, 1))
    visit[1] = 1

    while dq:
        vertex, weight = dq.popleft()
        for v in graph[vertex]:
            if visit[v] is False:
                visit[v] = weight + 1
                dq.append((v, weight + 1))
    return visit

def solution():
    N = int(input())
    M = int(input())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    visit = BFS(graph, N)
    ret = 0
    for v in visit:
        if 2 <= v < 4:
            ret += 1
    print(ret)

solution()

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

Categories:

Updated:

Leave a comment