[백준, BOJ 1058] 친구 (java)

https://www.acmicpc.net/problem/1058

1058번: 친구

---

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

728x90

 

예제 입력 1

3
NYY
YNY
YYN

예제 출력 1

2

 

예제 입력 2

3
NNN
NNN
NNN

예제 출력 2

0

 

예제 입력 3

5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN

예제 출력 3

4

 

예제 입력 4

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

예제 출력 4

8

 

예제 입력 5

15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

예제 출력 5

6

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 사람의 수 N 입력
		int N = Integer.parseInt(br.readLine());
		
		// 친구 정보 입력
		char[][] friends = new char[N][N];
		for (int i = 0; i < N; i++) {
			friends[i] = br.readLine().toCharArray();
		}
		
		// 플로이드 워셜
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) {
					// 본인이 아니고 서로 친구도 아닌 경우에
					if(j != k && friends[j][k] == 'N')
						// 친구의 친구라면
						if(friends[j][i] == 'Y' && friends[i][k] == 'Y')
							friends[j][k] = 'F'; // 'F'로 표시
				}
			}
		}
		
		// 가장 유명한 사람의 친구의 수 구하기
		int result = 0;
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = 0; j < N; j++)
				// 친구거나 친구의 친구라면 카운트
				if(friends[i][j] == 'Y' || friends[i][j] == 'F') sum++;
			result = Math.max(result, sum);
		}
		
		// 출력
		System.out.println(result);
	}

}