[SWEA] 5521. 상원이의 생일파티 - python

https://swexpertacademy.com/

SW Expert Academy

자세한 문제의 내용은 위 사이트의 수록된 문제로 5521. 상원이의 생일파티 를 검색하여 문제를 확인하면 된다.

 

문제풀이

• 상원이가 생일파티에 자신과 친한 친구와 친한친구의 친한친구에게 초대장을 주는 상황
  • 그래프로 표현할 수 있음
• 나눠 줘야하는 초대장의 수를 구하는 문제이고 1번이 상원이임.
  • 그래프를 탐색하여 해결할 수 있고, 탐색 시작이 1번임을 알 수 있음.

• 친한친구의 친한친구까지 탐색
  • 너비우선탐색 (BFS)을 이용하여 해결할 수 있고, 탐색의 너비를 2로 제한함.
  • que에 담긴 요소의 갯수를 저장하고 이를 이용해서 한번의 bfs탐색( 위 그림의 노란선)이 종료될 때 마다 거리(dist) 를 하나씩 늘려나가고 거리가 2가 되면 빠져나감.

소스코드(python)

	def bfs(v):
	    q = []
	    q.append(v)
	    visited[v] = 1
	    cnt = 0
	    dist = 0
	    while q:
	        s = len(q)
	        for j in range(s):
	            t = q.pop(0)
	            for i in adj[t]:
	                if visited[i] == 0:
	                    q.append(i)
	                    visited[i] = 1
	                    cnt += 1
	        dist +=1
	        if dist == 2: break
	    return cnt
	T = int(input())
	for tc in range(1,T+1):
	    N,M = map(int,input().split())
	    adj = {i :[] for i in range(N+1)}
	    for i in range(M):
	        a,b = map(int,input().split())
	        adj[a].append(b)
	        adj[b].append(a)
	    visited = [0]* (N+1)
	    print('#{} {}'.format(tc,bfs(1)))