바람에 흩날리는
면접 대비시간 제한2초메모리 제한512 MB
연결된 무방향 그래프에서 각 정점이 일부 삶의 목표를 이룰 수 있을 때, 1번 정점에서 출발해 목표 1부터 g까지 순서대로 이루는 데 필요한 최소 이동 횟수를 구합니다.
문제
1968년 시위 운동의 중요한 부분 중 하나는 시위 노래, 즉 사회의식이나 저항을 담은 가사를 단순한 포크풍 음악에 얹은 노래들이었다. 대표적인 곡 중 하나는 밥 딜런2의 "Blowin' in the Wind"로, "한 사람이 사람이라 불리기까지 몇 개의 길을 걸어야 하는가?"라는 가사로 시작한다. 딜런이 사람됨의 기준이 걸어야 하는 길의 최소 개수라고 말하려던 것은 아니고, 길은 한 사람이 겪는 인생 경험을 비유적으로 나타낸 것이다. 이 문제에서는 필요한 모든 인생 경험을 올바른 순서로 쌓기 위해 걸어야 하는 최소 길의 개수를 구한다.
주어진 순서대로 달성해야 하는 몇 가지 인생 목표가 주어진다. 또 연결된 무방향 그래프도 주어진다. 각 인생 목표마다 그 목표를 달성할 수 있는 노드가 그래프에 적어도 하나 있다. 출발 노드(항상 노드 1)에서 시작해 모든 인생 목표를 달성할 때까지 지나야 하는 길(간선)의 최소 개수를 구하라.
2 2016년 노벨 문학상 수상자이다.
입력
첫 줄에는 파일에 들어 있는 입력 데이터 세트의 수 K ≥ 1이 주어진다. 이어서 다음과 같은 형식의 데이터 세트 K개가 주어진다.
데이터 세트의 첫 줄에는 두 정수 1 ≤ g ≤ 20과 1 ≤ n ≤ 100이 주어진다. g는 인생 목표의 수이고 n은 그래프의 노드 수이다.
이어서 n개의 줄이 주어지며, 각 줄 i = 1, 2, . . . , n은 노드 i를 설명한다. 각 줄은 g개의 정수 ai,j ∈ {0, 1}로 시작하는데, ai,j = 1이면 노드 i에서 인생 목표 j를 달성할 수 있다는 뜻이다. 줄의 나머지 항목은 {1, 2, . . . , n}에 속하는 정수이며 노드 i의 간선을 설명한다. 간선은 무방향이다. 같은 간선이 목록에 여러 번 나타날 수 있고, 간선 (i, j)가 노드 i의 목록에 있을 때 노드 j의 목록에도 있을 수도, 없을 수도 있는데 어느 쪽이든 노드 j에서 노드 i로 이동하는 데 사용할 수 있다.
출력
각 데이터 세트마다 먼저 "Data Set x:"를 한 줄에 단독으로 출력한다. x는 데이터 세트의 번호이다. 그다음 노드 1에서 시작해 1, 2, 3, . . . , g의 순서로 모든 인생 목표를 달성하기 위해 걸어야 하는 길의 최소 개수를 출력한다.
각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.