[알고리즘] 친구

package org.example.알고리즘.친구;

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

public class Main {
    public static void main(String[] args) {
        try (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();
            }
            
            int maxFriends = 0;
            for (int i = 0; i < N; i++) {
                int count = 0;
                for (int j = 0; j < N; j++) {
                    if (i == j) {
                        continue;
                    }
                    // 직접 친구와 간접친구를 구함.
                    if (friends[i][j] == 'Y' || hasCommonFriend(friends, i, j)) {
                        count++;
                    }
                    maxFriends = Math.max(maxFriends, count);
                }
                
            }
            System.out.println(maxFriends);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
        
    }
    
    private static boolean hasCommonFriend(char[][] friends, int i, int j) {
        for (int k = 0; k < friends.length; k++) {
            if (friends[i][k] == 'Y' && friends[k][j] == 'Y') {
                // 0 2 와 2 1
                return true;
            }
        }
        return false;
    }
    
}

• 그래프 이론도 사실 필요없는 문제였다.

• 실제 직접친구가 몇명인지 확인

• 간접 친구 1 번 부터 N 까지
  • 내가 1번을 알고 있는지 → 1번은 다른 친구를 인지하는지 체크하여
  • 둘다 간접 친구가 알고 있다면 참 을 반환하여 총 친구의 수를 구할 수 있다.

Uploaded by N2T