단일 장애점(SPF)
면접 대비시간 제한1초메모리 제한128 MB
연결된 무방향 그래프마다 단절점을 모두 찾고, 그 정점을 제거했을 때 생기는 연결 성분의 개수를 구한다.
문제
P2P 네트워크에서는 물리적으로 직접 연결된 노드 사이에서만 데이터가 오갈 수 있다. 어떤 노드 하나가 고장 났을 때 남은 노드 가운데 적어도 한 쌍이 서로 통신할 수 없게 된다면, 그 노드를 단일 장애점(Single Point of Failure, SPF) 이라고 한다.
정확히 말하면, 이전에는 완전히 연결되어 있던(모든 노드가 서로 도달 가능한) 네트워크에서 어떤 노드를 제거했을 때 남은 노드들이 서로 도달할 수 없는 둘 이상의 그룹으로 나뉜다면, 그 노드가 SPF이다.
SPF가 하나도 없는 네트워크도 있다. 이런 경우에는 노드가 최소 두 개는 고장 나야 비로소 통신할 수 없는 노드 쌍이 생긴다. 주어진 각 네트워크에서 모든 SPF 노드를 찾아라.
입력
입력에는 여러 개의 네트워크가 들어 있다. 각 네트워크는 간선 목록으로 주어지며, 한 줄에 하나씩 직접 연결된 두 노드의 번호를 정수 쌍으로 적는다. 쌍 안에서의 순서는 의미가 없다. 즉 1 2와 2 1은 같은 연결을 나타낸다. 모든 노드 번호는 이상 이하이다.
0 하나만 있는 줄은 현재 네트워크의 간선 목록이 끝났음을 뜻한다. 간선이 하나도 없는 빈 네트워크(앞선 간선 없이 나오는 0)는 입력의 끝을 알린다. 빈 줄은 어디에 나오든 무시한다.
입력의 모든 네트워크는 어떤 노드가 고장 나기 전에는 완전히 연결되어 있다.
출력
각 네트워크마다 먼저 머리글 줄 Network #k를 출력한다. 여기서 k는 입력에서 그 네트워크의 순서이다(첫 번째 네트워크는 Network #1, 두 번째는 Network #2 …).
그다음, 각 SPF 노드에 대해 다음 형식의 줄을 출력한다.
SPF node <노드> leaves <개수> subnets
(앞에 공백 두 칸) 여기서 <노드>는 고장 난 노드 번호이고, <개수>는 그 노드가 고장 났을 때 남는 서로 분리된 완전 연결 서브넷의 수이다. SPF 노드는 노드 번호가 작은 순서대로 나열한다.
SPF 노드가 하나도 없으면 대신 No SPF nodes(앞에 공백 두 칸) 한 줄만 출력한다.
이어지는 두 네트워크의 출력 사이에는 빈 줄을 하나 넣는다.