PS/SCPC

[SCPC - 2018년 1차 예선] 우주정거장 (JAVA)

제이온 (Jayon) 2020. 8. 19.

문제

당신은 우주정거장을 설계하는 일을 맡게 되었다.
우주정거장은 공 모양의 캡슐들과 각각 두개의 캡슐을 연결하는 통로들로 만들어진다.
우주정거장이 최종적으로 어떻게 구성될지는 이미 정해져 있다고 한다.


우주정거장을 우주에 올리는 방법은 두단계로 이루어진다.
1단계에서 우주 정거장의 최초구성을 지상에서 만들어 궤도에 올린다. 2단계에서는 아래의 작업이 여러 차례 반복된다. 


- 작업 : 이미 통로로 직접 연결된 두 캡슐 A B에 대해서 A와 캡슐 X를 통로로 연결하고 B X를 통로로 연결한다.

 

여기서, 캡슐 X와 두 통로는 우주정거장에 새로 추가되는 것이다.



이 과정들 중에서 가장 많은 비용이 드는 과정은 1단계이다.
당신이 맡은 일은 1단계에서 만들어 올려야 하는 우주정거장의 최초구성에 포함된 캡슐의 개수가 가장 작도록 하는 것이다.
동일한 우주정거장의 최종구성에 대해 캡슐의 개수가 가장 작은 최초구성은 여러가지가 있을 수 있음에 주의하라.



다음 그림의 왼쪽의 경우는 5번 캡슐을 제외한 것이 캡슐 수가 가장 작은 최초 구성이다.
오른쪽의 경우는 1번을 제외, 2번을 제외, 3번을 제외하는 3가지 방법이 있다.

 

 

 



우주정거장의 최종구성을 입력으로 받아 캡슐의 개수가 가장 작은 최초 구성을 찾는 프로그램을 작성하시오.  

 

 

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 T 개의 테스트 케이스가 주어진다. (1T26)(1≤T≤26)



각 테스트 케이스의 첫 줄에는 최종 구성의 캡슐 수 N과 통로 수 M이 정수로 어진다.  (2N200,000,1M400,000)(2≤N≤200,000,1≤M≤400,000)


캡슐들은 1번부터 NN번까지 번호가 붙어 있다. 다음 MM개의 줄에 각 통로가 연결하는 캡슐 번호의 쌍이 하나씩 주어진다.


한 통로는 서로 다른 두 캡슐을 연결하며, 한 쌍의 캡슐을 연결하는 통로는 최대 1개이다.
임의의 캡슐에서 다른 임의의 캡슐로 1개 이상의 통로를 이용하여 이동하는 것이 가능함이 보장된다.

 

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에 가능한 최초구성 중 캡슐의 개수가 가장 작은 것에 대해서 그 캡슐의 개수를 정수로 출력한다. 

 

 

풀이

DFS를 이용하여 풀 수 있는 문제였습니다.

 

문제에서 주어진 그림을 보면 알 수 있듯이, 삼각형 모양의 사이클을 찾는 것이 중요했습니다.

특정 노드(start)와 연결된 간선이 2개일 경우, 연결된 노드 A와 B가 서로 연결되어 있는지 확인하면 됩니다.

 

이것은 DFS를 통해서 할 수 있으며, 최종적으로 A와 B도 연결된 삼각형 사이클을 이룬다면, start - A, start - B의 간선을 제거해 주면 됩니다.

 

다만, 주의할 점이 하나 있습니다. 아래 그림을 한 번 봅시다.

 

 

 

 

위 그림 상에서, 삼각형 사이클에 해당하는 노드는 6입니다. 따라서 2 - 6, 5 - 6의 간선을 지울 수 있습니다.

다만, 노드 6에 대한 간선이 사라지면서, 노드 5가 새로운 삼각형 사이클을 이루게 됩니다.

 

 

 

 

위 그림에서 알 수 있듯이, 추가적으로 이 노드 5에 대한 간선 2 - 5, 4 - 5를 지울 수 있습니다.

 

저는 처음에 단순히 노드 1부터 노드 6까지 순차적으로 간선의 개수가 2개인지 파악하고, A와 B 노드가 연결되어있는지만 파악하여 틀렸습니다.

 

따라서, 새롭게 삼각형 사이클 노드가 추가되는 것을 고려하기 위하여 노드 1부터 노드 6까지 순차적으로 탐색하는 과정을 100번 정도 반복하면 AC를 받을 수 있습니다.

 

문제를 여러 번 제출해 보니까 노드 1부터 노드 6까지 순차적으로 탐색하는 과정을 15번만 반복해도 AC를 받는 데 무리가 없었습니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

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

댓글

추천 글