PS/알고스팟

[AOJ] 알고스팟 : PICNIC (JAVA)

제이온 (Jayon) 2020. 9. 9.

문제

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

 

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

 

 

  • (태연,제시카) (써니,티파니) (효연,유리)
  • (태연,제시카) (써니,유리) (효연,티파니)

 

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

 

 

출력

각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다

 

 

풀이

인접행렬과 재귀를 이용하여 풀 수 있는 문제였습니다.

전반적인 로직은 아래와 같습니다.

 

 

1. 친구 관계를 인접 행렬로 입력 받는다.

 

2. 번호가 작은 친구부터 시작하여, 아직 짝을 맺지 못한 친구를 찾는다.

 

2-1. 만약, 모든 짝을 찾은 상태라면, 가능한 방법을 1개 찾은 것이다.

 

3. 짝은 맺지 못한 친구보다 숫자가 큰 친구 중에서 친구 관계에 속하는 짝을 찾는다.

 

 

위 과정을 반복하여 모든 친구에게 짝을 만들어 줄 수 있는 경우의 수를 구하면 됩니다.

자세한 소스코드는 아래를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.

'PS > 알고스팟' 카테고리의 다른 글

[AOJ] 알고스팟 : FESTIVAL (JAVA)  (0) 2020.09.14

댓글

추천 글