시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 343 | 97 | 47 | 20.172% |
임베디드 개발자인 진우는 방구석에서 데이터 시트만 보며 허무한 학창 시절을 보냈다. 하지만 주변 친구들의 수많은 구원의 손길 끝에, 소개팅에서 만난 한콩이와 장거리 연애를 시작했다! 모태솔로였던 진우의 고백은 마치 러블리즈의 곡 Close To You가 생각나는 장면이었다.
진우는 두근거리는 첫 데이트를 앞두고 있다. 진우는 이번 첫 데이트를 통해 한콩이에게 섬세하고 꼼꼼한 남자친구의 이미지를 각인시키려고 한다. 단순무식한 진우는 약속된 시간 동안 돌아다닐 수 있는 데이트 동선의 모든 경우의 수를 시뮬레이션해서 여러 상황을 대비하기로 결정했다.
바야흐로 언택트 시대, 진우는 차량을 렌트해 한콩이와 드라이브를 하기로 했다. 이를 위해 진우는 미리 지도에 N개의 동네를 표시해두었다. 그리고 한콩이를 데리러 가기 좋은 동네의 집합 P와 한콩이를 바래다 주기 좋은 동네 집합 Q를 정했다. 참고로, 집합 P와 집합 Q의 교집합에 속하는 동네가 존재할 수 있다.
진우의 지도는 그래프 구조로 그려져 있다. 동네를 각 정점으로 하고 양방향 간선으로 도로를 표현한다. 도로는 항상 서로 다른 두 동네를 이어주며, 도로를 통해 이동하는 시간은 항상 1이라고 가정한다. 진우의 드라이브 규칙은 다음과 같다.
뼛속까지 공대생인 진우는 위의 규칙을 칼같이 지키며 드라이브를 하려고 한다. 진우가 [1, K]의 시간 동안 드라이브를 할 수 있을 때, 발생할 수 있는 드라이브 경로의 수는 몇 가지인지 계산하는 프로그램을 작성하시오.
경우의 수가 너무 클 수 있으므로 1,000,000,007
로 나눈 나머지를 출력한다.
첫 번째 줄에는 세 개의 자연수 N, M, K가 공백으로 구분되어 주어진다.
이후 총 M개의 간선의 정보가 한 줄에 하나씩 주어진다
U V
형식으로 주어진다. (단, U ≠ V )(M+2)번째 줄에는 두 개의 정수 |P|, |Q|가 주어진다.
(M+3)번째 줄에는 P 그룹에 해당하는 동네의 번호가 공백으로 구분되어 주어진다.
(M+4)번째 줄에는 Q 그룹에 해당하는 동네의 번호가 공백으로 구분되어 주어진다.
[1, K]의 시간동안 발생할 수 있는 드라이브 경로의 수는 몇 가지인지 출력하시오.
1,000,000,007
로 나눈 나머지를 출력한다.6 6 2 4 1 5 1 2 1 2 5 5 6 3 6 2 3 1 2 6 5 2
10
6 3 2 1 4 5 2 3 6 3 3 1 2 3 6 5 4
3
6 3 100 1 4 2 5 3 6 3 2 1 4 2 3 6
0
University > 경인지역 6개대학 연합 > shake! 2020 E번