종점
시간 제한2초메모리 제한128 MB
최대 15개 도시로 이루어진 연결 그래프에서 차수가 정확히 1인 정점의 수를 최대화하는 신장 트리를 찾는 문제입니다.
문제
N개의 도시가 있고, 일부 도시 쌍은 양방향 도로로 연결되어 있다. 처음 주어지는 도로망에서는 어떤 두 도시 사이에도 경로가 존재한다.
도로 관리 비용을 줄이기 위해 일부 도로를 폐쇄하려고 한다. 도로를 최대한 많이 없애더라도, 남은 도로만으로 모든 도시 사이에 경로가 존재해야 한다.
남은 도로망에서 어떤 도시가 정확히 하나의 다른 도시와 직접 연결되어 있으면 그 도시를 종점이라고 한다. 주어진 도로 중 일부만 남겨 연결성을 유지할 때 만들 수 있는 종점의 최대 개수를 구하라.
입력
첫째 줄에 도시의 개수 N이 주어진다. N은 15 이하이다.
둘째 줄부터 N개의 줄에 인접행렬이 주어진다. 각 줄의 j번째 문자가 1이면 해당 줄의 도시와 j번째 도시 사이에 도로가 있고, 0이면 없다.
출력
종점의 최대 개수를 출력한다.