[BOJ 25172] 백준 25172번 - 꼼꼼한 쿠기의 졸업여행

		제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) 풀이
A		[BOJ 25165] 영리한 아리의 포탈 타기
B		[BOJ 25166] 배고픈 아리의 샌드위치 구매하기
C		[BOJ 25167] 이상한 아리의 채점
F		[BOJ 25170] 명랑한 아리의 외출
H		[BOJ 25172] 꼼꼼한 쿠기의 졸업여행
I		[BOJ 25174] 힘겨운 쿠기의 식당 개업기

1. 문제

$25172$. 꼼꼼한 쿠기의 졸업여행 (제4회 가톨릭대학교 프로그래밍 경진대회 (CCPC) H번)

백준 25172번 - 꼼꼼한 쿠기의 졸업여행 (https://www.acmicpc.net/problem/25172)

2. 풀이

문제는 완성된 그래프에서 노드와 그 노드에 연결된 간선을 제거하는 것이지만, 문제를 풀기 위해서는 빈 공간에 노드와 그 노드에 연결된 간선을 추가하는 방식으로 풀어야 한다.

문제에 있는 예제대로 4->5->1->2->3 순서로 노드를 제거한다고 가정해보자. 그럼 3->2->1->5->4 순서로 노드를 추가하게 된다. 과정은 다음 그림과 같다.

• 빨간색 실선 동그라미 $\rightarrow$ 추가된 노드
• 빨간색 실선 $\rightarrow$ 추가된 간선
• 빨간색 점선 $\rightarrow$ 확인한 간선
• 빨간색 점선 동그라미 $\rightarrow$ 확인한 간선과 연결된 노드
• 하늘색 네모 $\rightarrow$ 하나의 연결된 그래프 (group)

1. 노드를 추가한다. (GROUP += 1)
2. 추가하는 노드에 연결된 모든 간선을 확인한다.
3. 확인하는 간선에 연결된 노드 중 추가하는 노드가 아닌 다른 노드가 현재 존재할 경우, 해당 간선과 노드를 추가한다.
4. 간선과 노드를 추가할 때마다 Union and Find 알고리즘을 사용하여 group의 개수를 변화시킨다.
   • 추가하는 노드와 간선에 연결된 노드가 이미 동일한 group인 경우 => group 개수에 변함이 없다. (GROUP -= 1)
   • 추가하는 노드와 간선에 연결된 노드가 서로 다른 group인 경우 => group 개수가 하나 증가한다. (GROUP = GROUP)

현재 해당 노드가 존재하는지 확인해야 하기 때문에 따로 vector를 만들어 is_exist를 판단한다.

이상적인 여행계획은 GROUP=1인 경우이다. 따라서 이를 확인하여 정답을 만들어낸다.

3. 채점 결과

4. 회고

백준에서 비슷한 유형의 문제를 풀어봐서 방법을 쉽게 생각해낼 수 있었다.

5. 코드