Informatica Online Judge

  SNS 관계 [1186 / 04A2]

Time Limit(Test case) : 5000(ms)
Number of users who solved : 87   Total Tried : 461


The Champion of this Problem (C++) : gs15030 - ms / 376byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

경곽이는 이번에 새로운 SNS를 만들었다. n명의 학생들이 이러한 SNS에서 서로 관계를 맺고 있다. 친구 관계를 나타낼 때는 표를 이용하기로 했다. 예를 들어 3번 학생과 2번 학생이 친구관계를 맺고 있다면, 표의 2행 3열과 3행 2열의 값을 1로 표시한다. (단, 자신은 자기 자신과 친구가 아니다.)

경곽이가 만든 SNS는 a가 b의 친구이면 b도 a의 친구가 되는 구조이다. 하지만 직접적인 친구는 아니더라도, a가 b의 친구거나 친구일 가능성이 있으며, b가 c의 친구이거나 친구일 가능성이 있으면, a는 c와 친구가 될 가능성이 있다.

이번에 경곽이는 서로 친구이거나 친구가 될 가능성이 있는 모든 관계를 조사하고자 한다. 경곽이를 도와주는 프로그램을 작성하시오.

Input

첫 번째 줄에 SNS에 가입한 학생의 수를 나타내는 정수 n이 입력된다.
두 번째 줄부터 n줄에 걸쳐서 친구의 관계를 나타내는 길이가 n인 문자열이 입력된다. 문자열의 값 중 0은 친구가 아닌 관계, 1은 친구인 관계를 나타낸다.

[Sub-Task Info]
#1 : n <= 10 (40%)
#2 : n <= 200 (40%)
#3 : n <= 1,000 (20%)

Output

n행에 걸쳐서 각 줄에 n개의 0 또는 1을 공백으로 구분하여 출력한다.
각 값 (a, b)의 값은 학생 a와 학생 b가 서로 친구이거나 친구가 될 가능성이 있다면 1, 그렇지 않으면 0으로 나타낸다.

IO Example

입력
3
010
101
010

출력
0 1 1
1 0 1
1 1 0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]