import copy #연결성분의 개수를 카운트하기 위해 고안한 코드입니다. #실행 시 어느 점 i와 연결된 모든 점들을 '2'로 채우게 됩니다. def spread(a,i): a[i]='2' for m in range(12): if array[i][m]==1: if a[m]=='1': spread(a,m) #array는 정이십면체를 그래프로 나타낸 것입니다. #결과가 의심되면 직접 만들어봅시다!! array=[[0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0], [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0], [1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0], [1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0], [0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1], [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1], [0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0]] #answer는 조각수열을 의미합니다. answer=[0 for i in range(13)] #아래 for문은 12개의 점들 중에서 일부 점들을 선택해서 조각수열을 구하는 과정입니다. #일종의 더블카운팅으로 생각해주시면 될 것 같습니다. #i를 12자리 이진수로 나타내면 각 점들을 어떻게 선택했는지 보기가 편하죠 #ex. i=7이면 이진수로 000000000111 -> 10, 11, 12번째 점을 선택한 것 for i in range(2**12):#선택하는 가짓수는 2^12개 #이건 i를 12자리 이진수로 만드는 코드 x=list(bin(i)) x.pop(0); x.pop(0) y=['0' for _ in range(12-len(x))] y.extend(x) #n은 선택한 점의 개수를 의미합니다. n=12 #선택한 점들로 유도되는 새로운 그래프를 만드는 코드 new_arr=copy.deepcopy(array) for j in range(12): if y[j]=='0': n-=1 for k in range(12): new_arr[j][k]=0 new_arr[k][j]=0 #number는 (연결성분의 개수-1) 을 나타내게 됩니다 number=0 #연결성분의 개수를 세는 코드입니다. for j in range(12): if y[j]=='1': number+=1 spread(y,j) number-=1 #문제에서 b_j를 구할 때 1을 빼라고 요구합니다. answer[n]+=number #이제 b_n에 (연결성분의 개수-1)을 더해줍니다. #답 출력 for i in range(2,9+1): print(answer[i],end=' ')