경기도 정보올림피아드 알고리즘- 가족 찾기 > 문제은행 : 정보올림피아드&알고리즘



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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP