[BaekJoon] 1058 친구

1.  문제 링크

2.  문제

요약

• 주어진 사람들 중에서 가장 유명한 사람을 구하는 문제인데 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람입니다.
• 어떤 사람 A가 B의 2-친구가 되기 위해서는 A와 B가 친구이거나 A와 친구이고 B와 친구인 사람이 존재해야 합니다.
• 입력: 첫 번째 줄에는 사람의 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 각 줄에 각 사람이 친구이면 Y, 아니면 N이 주어집니다.
• 출력: 가장 유명한 사람의 2-친구 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
	public int getMaxFriend(ArrayList<String> isfriend) {
		int max_num = 0;
		for(int i = 0; i < isfriend.size(); i++) {
			HashSet<Integer> friends = new HashSet<Integer>();
			for(int j = 0; j < isfriend.size(); j++) {
				if(isfriend.get(j).charAt(i) == 'Y') {
					friends.add(j);
				}
			}
			ArrayList<Integer> i_friends = new ArrayList<Integer>();
			for(int j = 0; j < isfriend.get(i).length(); j++) {
				if(isfriend.get(i).charAt(j) == 'Y') {
					i_friends.add(j);
				}
			}
			for(int j = 0; j < i_friends.size(); j++) {
				for(int k = 0; k < isfriend.size(); k++) {
					if(k == i) {
						continue;
					}
					if(isfriend.get(k).charAt(i_friends.get(j)) == 'Y') {
						friends.add(k);
					}
				}
			}
			if(max_num < friends.size())
				max_num = friends.size();
		}
		return max_num;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<String> isfriend = new ArrayList<String>();
		for(int i = 0; i < num; i++) {
			String friend = br.readLine();
			isfriend.add(friend);
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxFriend(isfriend) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 각 사람들의 2-친구 수를 구하여 그 중 가장 많은 사람의 2-친구 수를 출력하면 되는 문제입니다.
• 2-친구 수를 구하는 방법은 위 조건에서 주어진대로 두 사람이 친구이거나 두 사람이 같이 친구를 하고 있는 사람을 구하면 됩니다.
• 두 사람이 친구인지는 주어진 문자열을 통해 두 사람 사이에 Y인지 N인지를 보고 판단할 수 있습니다.
• 두 사람이 같이 친구를 하고 있는 사람을 구하는 방법은 한 사람의 친구 목록을 보고 그 사람을 제외한 다른 사람 중에서 친구 목록에 있는 사람 중 한 명과만이라도 친구를 하고 있는 사람을 구하면 됩니다.
• 이러한 방법을 통해 각 사람마다 2-친구의 수를 구하고 그 중 가장 많은 사람의 2-친구 수를 출력합니다.