[Python] 백준 5567번 : 결혼식

문제

5567번: 결혼식

[ 문제 조건 ]

• n : 동기의 수 (즉, 숫자의 종류)
• m : 친구 관계 나타내는 리스트 개수

[ 해결순서 ]

1. 상근이는 결혼식에 자신의 친구 + 친구의 친구까지 초대 가능하므로 너비우선탐색을 이용해서
2. 자신의 친구먼저 몇명인지 탐색 후 친구의 친구까지 탐색한다.
3. bfs 메소드를 이용해서 친구 1명을 먼저 구한다음
4. 그 친구의 친구까지 탐색하고 다음 친구의 친구의 친구 탐색하고 초대인원 값 + 1하면
5. 깊이를 계산해서 깊이가 2이면 (친구의 친구까지만 초대가능하므로) 총 초대인원 출력하고 종료한다.

✏️한줄평

: 처음에 이진트리를 생각해서 그렇게 풀려고 했는데 사실 굳이 그럴필요 없이 그냥 bfs로 친구들 탐색하고 깊이 +1 하다보면 구해지는 문제였다.

---

코드

	from collections import deque
	def bfs(start):
	dq = deque()
	dq.append(start)
	visited[start] = True #1은 방문처리
	count = 0 #초대할 사람이 몇 명인지
	depth = 0 #깊이가 2이면 끝
	while dq:
	depth += 1
	for _ in range(len(dq)):
	friend = dq.popleft()
	for val in list[friend]:
	if not(visited[val]):
	visited[val] = True
	dq.append(val)
	count += 1
	if depth == 2:
	print(count)
	break
	n = int(input())
	m = int(input())
	list = [[] for _ in range(n+1)] #n명의 친구관계를 나타내야 함
	visited = [False] * (n+1)
	#양방향 그래프로 연결
	for _ in range(m):
	a, b = map(int,input().split())
	list[a].append(b)
	list[b].append(a)
	bfs(1)

view raw BOJ5567.py hosted with ❤ by GitHub