알고스팟(Algospot): 피크닉(PICNIC) [C++]

문제 출처: algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

1. 코드

(실행)

 

2. 풀이

-문제 설명

우선 이 문제는 개인적으로 문제부터 이해하기가 많이 힘든 문제였다. 그렇기 때문에 우선 문제에 대해 먼저 알아보자. 예제 입력에서 학생의 수를 4라고 하면  친구 쌍의 수가 6이라고 하면 0 1 1 2 2 3 3 0 0 2 1 3가 순서대로 입력되었는데 친구 쌍의 수는 6이라는 의미는 실질적으로 12명이 있다는 말이다. 그렇기에 12개의 서로 친구인 두 학생의 번호가 주어집니다. 입력에서는 저렇게 입력이 되었지만 실질적인 입력은 다음과 같다. (0, 1) (1, 2) (2, 3) (3, 0) (0, 2) (1, 3) 이렇게 6쌍이라는 것이다.

그렇다면 4는 무엇을 의미하는가? 그것은 바로 한 줄에 학생을 친구끼리만 짝지어주는 인원수이다. 조금 더 쉽게 설명하겠다. 문제를 보면 학생들을 친구끼리 짝을 지어준다고 하는데 그렇다면 짝의 수가 존재하는데 그 수이다. 즉, (0, 1) (2, 3)으로 짝이 지어졌다. 그렇다면 친구끼리 모인 학생의 수는 4이다. 그리고 친구끼리만 모여야 하기에 같은 수가 존재하면 안 된다. 그렇게 해서 학생의 수가 4이고, 친구 쌍의 수가 6이면 (0, 1) (2, 3)와 (1 2) (3 0) 그리고 (0 2) (1 3)이다. 그래서 총 3가지 경우이다.

-풀이 설명

이제 풀이에 대한 설명이다. 배열 f를 이용하여 친구를 식별하게 만들었다. 친구일 경우에 배열의 값에 1을 저장하여 구별하였는데 x와 y로 친구 1, 2를 식별했는데 f [x][y] = f [y][x] = 1로 식별을 했다. 그리고 수가 가장 빠른 친구를 찾고 반복문을 짝이 되는 친구를 찾아내고 찾아내면 check 배열을 이용하여 구별해주고 재귀를 이용하여 다른 수들도 검사를 진행한다. 그리고 짝을 다 찾았을 때 result값에 1을 더해준다. 그리고 다른 경우 또한 검사를 해야 하기에 check의 값에 1로 구별해놓은 것을 0으로 초기화해준다.

 

3. 느낀 점

나는 사실 이 문제를 푸는데 전혀 감이 잡히지 않아 책을 보고 풀었는데 풀면 풀수록 재귀 함수에 대한 응용력의 미숙하다는 것에 계속해서 깨닫고 있는다. 그리고 문제를 이해하는데 거의 2일이 걸렸다. 그래서 문제 능력 이해도 부족하다고 느꼈다. 열심히 해야겠다.