가족 찾기 > 문제은행



문제은행

1714 : 가족 찾기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 16 회    시도횟수: 33 회   



건수네 학교에서 부모님들과 학생들이 모두 참석한 행사를 하고 있다. 행사 중 모든 사람들이 모여서 할 수 있는 놀이 중 가족 찾기가 있다. 다만 놀이에 모든 사람이 포함되는 것은 아니고 정사각형을 만들 수 있는 일부 사람들이 놀이에 참가한다. 놀이의 규칙은 다음과 같다

① 같은 가족이면 서로 좋아해야 한다.
② 같은 가족은 2명 이상이다
③ 다른 가족은 서로 싫어한다.

좋아하는 사람을 표시할 때는 1을 표시하고 싫어하는 사람을 표시할 때는 0를 표시한다.
예를 들어 아래와 같이 3명을 나타내는 정사각형은 다음과 같이 해석된다.

1 0 1 첫 번째 사람은 두 번째 사람을 싫어하고 세 번째 사람을 좋아한다.
0 1 0 두 번째 사람은 첫 번째 사람을 싫어하고 세 번째 사람도 싫어한다.
1 0 1 세 번째 사람은 첫 번째 사람을 좋아하고 두 번째 사람을 싫어한다.
따라서 첫 번째 사람과 세 번째 사람은 가족이다.

위와 같은 숫자들이 주어졌을 때 가족의 수와 가족 구성원을 구하는 프로그램을 작성하시오. 단 사람과 사람관계는 대칭성이 있어 A 가 B를 좋아하면 B도 A를 좋아하고 A가 B를 싫어하면 B도 A를 싫어한다.




입력 파일명은 "Input.txt"로 한다. 입력 파일의 첫째 줄에는 사람의 수 N이 주어진다. (N은 2이상 50이하)
두번째 줄부터 N+1 줄까지는 사람들의 관계가 숫자로 주어진다.(위 예 참조), 단 숫자 사이는 공백으로 분리된다.




출력 파일명은 "Output.txt"로 한다. 출력 파일의 첫째 줄에는 가족의 수(m)을 출력하고, 두 번째 줄부터 m+1 줄까지는 가족들의 구성원을 번호로 표시한다. 출력 순서는 가족 구성원의 숫자합(번호합)이 큰 순서부터 출력하고 각 가족 구성원은 작은 순서부터 출력한다.



5
1 0 0 1 1
0 1 1 0 0
0 1 1 0 0
1 0 0 1 1
1 0 0 1 1
2
1 4 5
2 3


3
1 0 1
0 1 0
1 0 1
1
1 3






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.