| 시간 제한 | 메모리 제한 |
| 1초 | 1024MB |
문제
그래프의 변환(f:g↦g′)을 다음과 같이 정의한다. G의 간선을 G'의 정점으로 보고 G의 인접한 간선끼리 G'에서 간선으로 연결하여 G에서 인접하였음을 나타낸다.
서로 다른 두 간선이 같은 정점을 하나 이상 공유하면 두 간선이 인접한다고 표현한다.
다음은 그래프 변환의 예시 중 하나이다.
그리고 변환한 그래프를 다시 변환하는 것도 가능하다.
N-완전 그래프를 K번 변환한 그래프의 정점이 몇 개인지 구하시오. N-완전 그래프는 정점이 N개인 그래프에서 서로 다른 두 정점에 대해 반드시 간선이 존재하는 그래프이다.
입력
첫째 줄에 정수 N, K가 공백을 사이에 두고 주어진다. (3 ≤ N ≤ 100,000, 0 ≤ K ≤ 100,000)
출력
K번 변환한 그래프의 정점의 개수를 1,000,000,007(=109 + 7)로 나눈 나머지를 출력한다. 이 수는 소수이다.
풀이
이 문제 그래프를 직접 그려보면 알겠지만 절대 2회 이상의 변환은 사람 손으로 할 만한 계산이 아니다. 이런 문제 수작업으로 규칙을 발견하는 방법을 주로 사용했기 때문에 굉장히 어려웠다.
먼저 그래프의 형태를 자세히 관찰할 필요가 있다. N-완전 그래프라면 어떤 그래프를 갖다 써도 똑같지만 본 풀이에서는 5-완전 그래프를 예시로 썼다. 그래프의 각 정점에 번호를 매겨놓고 연결된 다른 정점들을 표현해보면 아래와 같이 표현된다. 여기서 알 수 있는 사실은 모든 정점의 연결 상태가 똑같은 형태라는 점이다. 그러니까 1,2,3,4,5라고 번호를 붙여놓은 정점들의 번호를 아무렇게나 바꾸어 붙여도 사실 수학적으로는 똑같다.
각각의 정점들이 완전히 서로와 닮아있기 때문에 간선을 기준으로 봐도 똑같다. 어떤 간선 e를 보면 이 간선에 인접한 간선은 6개다. 이건 그래프 내의 어떤 간선을 선택해도 같다. 그 이유는 이렇다. 간선을 특정하기 위해서는 양 끝에 정점이 두 개 필요한데, 지금 우리가 보는 그래프는 어떤 정점을 골라도 그 형태가 똑같기 때문에 이 그래프에서 선택할 수 있는 모든 간선 e는 서로 닮아있다.
여기서부터 편의상 기존 그래프의 정점은 v, 기존 그래프의 간선은 e, 변환된 그래프의 정점은 v', 변환된 그래프의 간선은 e'로 부르겠다.
자, 그럼 5-완전 그래프는 총 10개(5×(5-1)÷2)의 간선e를 갖고 있으므로, 10개의 간선e는 10개의 정점v'이 된다. 그리고 기존 그래프에서 인접한 간선e들은 변환된 그래프에서 간선e'으로 연결되기 때문에 e는 변환되었을 때, 6개의 간선으로 다른 정점v'과 이어지게 된다. 10개의 간선e 모두가 똑같은 형태로 변환되었기 때문에 10개의 정점v' 모두가 6개의 간선e'을 갖는다. 그런데 모든 정점v'에 대해 간선e'을 계산해보면 e'이 모두 한번씩 중복되기 때문에 2로 나눠주면 간선e'의 수를 구할 수 있다.
이제 변환된 그래프인 G'의 간선 e'을 살펴보자. v'은 모두 6개의 간선을 갖는다고 했는데, e'을 특정하려면 또 두 개의 v'을 선택해야 한다. 두 정점v'가 갖고있는 간선은 12개이지만 이중 2개는 e'을 나타내기 때문에 e'을 제외하면 e'과 인접한 간선은 10개다. 그럼 여기서 다음 변환을 거쳐 G''의 정점v''과 간선e''의 수를 구할 수 있다.
n(v'') = n(e') = 30
n(e'') = [{(n(e')×2)÷n(v')-1}×2]×n(v'')÷2 = [{(하나의 정점에 연결된 간선의 수)-1}×2]×n(v'')÷2
= [하나의 간선에 인접한 간선의 수]×n(v'')÷2 = 150
두 번째 식이 좀 복잡한데 정리하면 이렇다.
설명을 하면 할 수록 점점 미궁이다...
아무튼 F:G->G' 변환에 필요한 것은 두 가지다. 원래 그래프의 정점의 수, 하나의 정점에 연결된 간선의 수
이 둘을 갖고 다음 G'의 정점과 한 정점에 연결된 간선의 수를 구할 수 있다. 이걸 반복하면 n번 변환을 수행한 후의 정점의 수를 구할 수 있다. 아래 표는 5-완전 그래프에서 4번까지 변환했을 때의 결과를 정리한 것이다. 다음 변환을 위해 넘겨지는 값을 색깔로 표시했다.
정답 코드
N,K = map(int,input().split())
# result = 얻고자 하는 정점의 수
# a = 한 정점에 연결된 간선의 수
result,a = N,N-2
if K == 0:
print(N)
else:
# 첫 번째 변환은 아래 식으로 수행
result = N*(N-1)//2
# 이후 변환
for _ in range(K-1):
result*=a
result%=1000000007
a*=2
a-=1
a%=1000000007
print(result)
