Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 3085 사탕 게임
백준 3085 사탕 게임
문제
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다.
상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다.
이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄: 상근이의 동기의 수 N
- 두번째 줄: 리스트의 길이 m
- 세번째 줄 ~: 친구 관계 ai bi
출력
상근이가 결혼식에 초대하는 동기의 수
해결 방식
bfs 알고리즘 이용
- visited에 몇 번을 거친 친구인지 저장
코드
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [ [] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
for i in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
def bfs(x):
q = deque()
visited[x] = 1
q.append(x)
while q:
a = q.popleft()
for i in graph[a]:
if visited[i] == 0:
q.append(i)
visited[i] = visited[a] + 1
bfs(1)
result = 0
for i in range(2,n+1):
if visited[i] < 4 and visited[i] != 0:
result += 1
print(result)
