[알고리즘] 결혼식

문제 링크

 

결혼식 : https://www.acmicpc.net/problem/5567

 

문제탐색

기본 원리 탐색

• 상근이를 기점으로 구성된 양방향 그래프에서 거리가 2인 노드수를 구하는 문제입니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 동기의 수  : 500명

거리가 2인 노드를 탐색하려면 범위탐색에 좋은 BFS를 사용할 수 있습니다. BFS의 시간복잡도는 O(N+m)으로 약 1만회로 문제없습니다.

 

하지만 거리가 2로 고정되어 있으므로 간단하게 그래프를 인접리스트로 구현한 뒤 상근이 친구의 친구들을 모두 집합으로 묶는 방법을 사용합니다.

=> 인접리스트를 활용한 집합연산을 수행합니다.

 

코드설계하기

1. 입력을 인접리스트로 받습니다.
2. 집합에 상근이와 상근이 친구를 포함합니다.
3. 상근이 친구들의 인접리스트를 집합으로 묶습니다.
4. 집합의 길이 -1 을 출력합니다. (상근이 제외)

 

시도회차 수정사항

 

정답코드

import sys
n=int(sys.stdin.readline())
m=int(sys.stdin.readline())

grp=[[] for x in range(n)] #인접리스트 생성

for x in range(m):
    a,b=sys.stdin.readline().split()
    a,b=int(a)-1,int(b)-1
    grp[a].append(b)
    grp[b].append(a)

party=set(grp[0])|set([0]) #상근이+상근이친구 파티에 초대

for x in grp[0]:
    party=party|set(grp[x]) #상근이 친구의 친구 파티에 초대

print(len(party)-1)#상근이 제외한 파티참가 인원