대경권

작년에 포인터도 기억못한 상태에서 꾸역꾸역 C로 풀었었는데 1년 새에 C++도 할줄 알게 되고 이런저런 코딩 결과물도 만들어 보게 됐다.

내가 진짜 늘긴 늘었는지 이번 기회를 통해 확인하고자 대회에 나오게 됐다..ㅎㅎ 물론 아직도 많이 부족하지만 말이다:)

물론 이게 다는 아니지만 그동안 프로그래머스를 통해서 공부하면서 조금은 내 실력이 성장한 걸 느낄 수 있어서 너무 기분이 좋다! 경북대 가기 전까지 열심히 또 해보자ㅎㅎ

문제

학생수가 N명인 어느 국제 학교에서 서로 다른 국적을 가진 학생 대표 두 명을 뽑으려 합니다. 이 학교에서는 국적을 파악하기 위해 학생에게 1부터 N까지 중복없이 번호를 붙이고, 같은 국적을 가진 학생 쌍을 기록해 뒀습니다. 이때, 대표 두 명을 뽑는 방법은 모두 몇 가지인지 구하려 합니다. 단, 어떤 두 학생 A, B의 국적 관계가 기록에 없고, 다른 학생들의 관계를 이용해서도 알아낼 수 없는 경우 A, B 두 학생의 국적은 항상 다릅니다.

예를 들어 학생 수가 4명이고, 기록 용지에 [1, 2], [2, 3], [1, 3] 이 적혀 있으면 4번 학생을 제외하고 [1, 2, 3] 번 학생이 같은 국적을 가지고 있습니다. 따라서 대표 두 명을 뽑는 방법은 (1, 4), (2, 4), (3, 4)로 총 3가지입니다.

전체 학생 수 N과 같은 국적인 학생 쌍이 주어질 때, 대표 두 명을 뽑는 방법은 모두 몇 가지인지 구해주세요.

제한사항

입력 :

  • 표준 입력을 사용해 데이터를 입력받으세요.
  • 테스트케이스 첫째 줄에 전체 학생 수 N(2 ≤ N ≤ 100, N은 자연수)과 같은 국적인 학생 쌍 기록의 수 K(1 ≤ K ≤ 1000, K는 자연수)가 주어집니다.
  • 그다음 줄부터 총 K 줄에 걸쳐 두 자연수 a, b가 주어집니다.
  • a, b는 각각 같은 국적을 가지는 두 후보의 번호를 나타냅니다.
  • a, b는 1 이상 N 이하인 자연수이며, a와 b가 같은 경우는 주어지지 않습니다.
  • 같은 학생 쌍에 대한 정보는 한 번씩만 주어집니다.

출력 :

  • 표준 출력을 사용해 정답을 출력하세요.
  • 대표 두 명을 뽑는 방법은 모두 몇 가지인지 출력하세요.
  • 대표 두 명을 뽑을 수 있는 방법이 없다면 0을 출력하세요.

입출력 예

입력 #1

4 3 1 2 2 3 1 3

출력 #1

3

입력 #2

5 2 1 2 2 3

출력 #2

7

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

[1, 2, 3] 번 학생이 같은 국적을 갖고 있으며, 4번, 5번 학생은 국적이 다릅니다.

따라서 대표를 뽑는 방법은 (1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5), (4, 5) 총 7가지입니다.

문제 풀이

  • 전에 풀어본 문제와 비슷한 문제가 나왔다! 일단 조합을 이용해야 할듯 하다!
  • 먼저 대표 2명을 뽑는 모든 경우의 수는 N*(N-1)/2 이다!
  • 이 때 각 학생들이 같은 국적을 가지고 있다면 그 경우를 제외해주면 된다.
  • 즉, cycle을 이루고 있는 얘들의 개수(C)를 파악한 후에 전체 경우의 수에서 에서 빼주면 된다.
  • 전체 경우의 수 - 각 싸이클의 원소들로 이주어진 경우의 수
  • 여기서 싸이클을 찾는 방법에 BFS를 사용했다.
  • Cycle이 발견되면 그 즉시 전체 경우의 수에서 해당 원소들로 이루어질 경우의 수를 빼주었다.
  • 조합을 생각해내고 BFS 등을 이용하여 Cycle을 발견할 수 있다면 문제를 풀 수 있을 것이다.
  • BFS 이용코드는 DFS/BFS 문제 풀이를 참고 하면 좋을 것 같다 ㅎㅎ

결론

  • 작년보다 실력이 는거가 보여서 진짜 기분이 좋다.
  • 그동안 프로그래머스 문제를 풀어본 보람을 느낄 수 있어서 너무 기분 좋은 시간이었다.
  • 본선에서 물론 광탈하겠지만 다음주 동안 빡 공부해서 조금이라도 성과를 내보고 오자! ㅎㅎ