[Java] 백준 1058번 : 친구

문제

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

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

입력

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

출력

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

예제 입력 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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N;
	private static char [][] map;
	private static List<Integer> list;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		map=new char[N][N];
		HashMap<Integer, List> friends=new HashMap<>();
		HashMap<Integer, List> plus=new HashMap<>();
		
		for(int r=0;r<N;r++) {
			st=new StringTokenizer(bf.readLine());
			map[r]=st.nextToken().toCharArray();
		}
		
		for(int r=0;r<N;r++) {
			list=new ArrayList<>();
			for(int c=0;c<N;c++) {
				if(map[r][c]=='Y') {
					list.add(c);	// 1친구를 list에 모두 저장
				}
			}
			friends.put(r, list);	// 1친구를 map에 모두 저장
		}
		for(int i=0;i<N;i++) {
			List li=new ArrayList<>();
			List friends1=friends.get(i);	// 1친구에 대해 2친구를 탐색
			int size1=friends1.size();
			for(int j=0;j<size1;j++) {
				List friends2=friends.get(friends1.get(j));	// 2친구 중 가능한 친구 리스트를 탐색하러 감
				int size2=friends2.size();
				for(int k=0;k<size2;k++) {	// 자기 자신이 아니면서 2친구이면 plus 리스트에 추가함
					if((int)friends2.get(k)!=i && !friends1.contains(friends2.get(k)) && !li.contains(friends2.get(k))) {
						li.add(friends2.get(k));
					}
				}
			}
			plus.put(i, li);
		}

		int maxVal=0;
		for(int i=0;i<N;i++) {	// 1친구와 2친구 수의 합이 최대인 값을 찾음
			int tmp=friends.get(i).size()+plus.get(i).size();
			maxVal=Math.max(maxVal, tmp);
		}
		System.out.println(maxVal);
	}

}