[백준] 5567(파이썬) - 결혼식

[백준] 5567(파이썬) - 결혼식

728x90

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

이 문제를 처음 읽고 든 생각은 '어쨌든 그래프니까 bfs를 이용해야겠다'였습니다.

bfs로 풀다 보니 생각보다 로직이 간단했습니다.

bfs로직을 풀 때, 부모 노드에서 자식 노드로 갈 때 visited [부모 노드]에서 +1을 해서 visited [자식 노드] 값으로 넣어줬습니다.

그러면 visited에 담기는 값이 1번부터 시작해서 몇 번을 거친 친구인지가 나오게 되는데, 조건에서 친구의 친구까지만 초대를 한다고 했으니까 visited 가 4보다 작을 경우만 result += 1을 해줘서 정답을 구했습니다.

import sys input = sys.stdin.readline from collections import deque n = int(input()) m = int(input()) graph = [ [0] * (n+1) 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): # 본인이거나 친구거나, 친구의 친구거나 경우의 수가 최대 3개 if visited[i] < 4 and visited[i] != 0: result += 1 print(result)

from http://resilient-923.tistory.com/354 by ccl(A) rewrite - 2021-11-24 23:00:10