문제 설명
세종이네 학급에는 총 N명의 학생이 있다. 학생들은 서로 친한 친구에게만 번호를 공유하며, 번호가 없는 친구에게는 연락을 할 수 없다. 코로나19로 인한 온라인 수업 중 공지사항이 생긴 경우에 세종이의 담임 선생님은 항상 모든 학생들에게 일일이 공지사항을 보냈다. 매번 모든 학생들에게 공지사항을 보내는 게 힘들었던 선생님은 다음과 같은 학급 규칙을 만들었다.
"만약 공지사항을 전달받았다면, 자신이 번호를 알고 있는 모든 친구들에게 공지사항을 전달해야 한다. 단, 이전에 전달했던 공지사항을 다시 받았다면 전달할 필요가 없다."
세종이네 학급의 모든 학생들이 위 규칙을 준수한다고 할 때, 모든 학생들에게 공지사항을 전달될 수 있도록 하기 위해 세종이의 담임선생님은 최소 몇 명의 학생에게 공지사항을 보내야 하는지를 구하는 프로그램을 작성하시오.
"만약 공지사항을 전달받았다면, 자신이 번호를 알고 있는 모든 친구들에게 공지사항을 전달해야 한다. 단, 이전에 전달했던 공지사항을 다시 받았다면 전달할 필요가 없다."
세종이네 학급의 모든 학생들이 위 규칙을 준수한다고 할 때, 모든 학생들에게 공지사항을 전달될 수 있도록 하기 위해 세종이의 담임선생님은 최소 몇 명의 학생에게 공지사항을 보내야 하는지를 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에는 학생의 수 \(N\)이 주어진다.\((1 \le N \le 1,000)\)
다음 \(N\)개의 줄에는 \(N\)개의 수가 입력된다. \(i\)번째 줄의 \(j\)번째 수는 \(i\)번 학생과 \(j\)번 학생의 친한 정도를 의미한다. \(1\)은 친한 사이, \(0\)은 친하지 않은 사이이며, \(i\)와 \(j\)가 친하다면 \(j\)와 \(i\)도 친하다.
다음 \(N\)개의 줄에는 \(N\)개의 수가 입력된다. \(i\)번째 줄의 \(j\)번째 수는 \(i\)번 학생과 \(j\)번 학생의 친한 정도를 의미한다. \(1\)은 친한 사이, \(0\)은 친하지 않은 사이이며, \(i\)와 \(j\)가 친하다면 \(j\)와 \(i\)도 친하다.
출력 설명
세종이네 담임 선생님이 공지사항을 보낼 학생 수의 최솟값을 출력한다.
입력 예시 Copy
5
0 0 1 0 1
0 0 0 1 0
1 0 0 0 1
0 1 0 0 0
1 0 1 0 0
출력 예시 Copy
2