시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 167 | 53 | 44 | 34.921% |
세준이의 나라에는 N개의 도시가 있다. 몇몇 도시들은 양방향 도로로 서로 연결되어 있다. 그리고, 모든 도시는 서로에게 가는 경로가 존재한다.
세준이는 어느 날 이렇게 많은 도로를 관리하는 것이 너무 비싸다고 생각했기 때문에, 몇 개의 도로를 폐쇄해 버리려고 한다. 세준이는 되도록 많은 도로를 폐쇄하려고 한다. 그러나, 세준이는 모든 도시가 서로에게 가는 경로가 존재해야 한다고 생각한다.
종점이란 것은 어떤 도시가 단 하나의 도시와 연결되어 있을 때, 종점이라고 한다. 현재 도로가 연결된 상태가 주어질 때, 종점의 개수를 최대로 하는 프로그램을 작성하시오.
첫째 줄에 도시의 개수 N이 주어진다. N은 15보다 작거나 같다. 둘째 줄부터 N개의 줄에 인접행렬이 주어진다.
종점의 최대 개수를 출력한다.
5 01000 10100 01010 00101 00010
2
2 01 10
2
5 01111 10000 10000 10000 10000
4
4 0111 1011 1101 1110
3
10 0100000001 1010000000 0101000000 0010100000 0001010000 0000101000 0000010100 0000001010 0000000101 1000000010
2