BOJ 1058 - 친구 | 안성진

문제

BOJ 1058 - 친구

N명의 사람이 있을 때, 직접 친구이거나 공통 친구가 1명 있으면 2-친구라고 한다. 각 사람의 2-친구의 최댓값을 구하는 문제이다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

다음 N줄에 각 사람의 친구 관계가 주어진다. Y는 친구, N은 친구가 아닌 경우이다.

출력

2-친구의 수의 최댓값을 출력한다.

예제

입력:

3
NYY
YNY
YYN

출력:

풀이

핵심 아이디어: 플로이드-워셜 알고리즘으로 모든 쌍의 최단 경로를 구한다. 직접 친구는 거리 1, 공통 친구를 통한 경우는 거리 2이므로, 최단 거리가 2 이하인 사람의 수가 2-친구의 수이다.

단계별 풀이:

친구 관계를 인접 행렬로 표현. 친구면 1, 비친구(자신 제외)면 매우 큰 값(무한대)으로 초기화.
플로이드-워셜을 수행하여 모든 쌍 최단 경로 계산.
각 사람 i에 대해, arr[i][j] <= 2인 j의 수를 세어 2-친구 수를 구한다.
모든 사람 중 최댓값을 출력한다.

플로이드-워셜을 선택한 이유: N이 최대 50으로 작아 O(N³) 알고리즘이 충분히 빠르다.

코드

package com.ssafy.an.day199;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Day180BOJ1058플루이드와샬 { // 1058 플루이드 와샬
	static int N, result = 0;
	static int arr[][];
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			String str = br.readLine();
			for (int j = 1; j <= N; j++) {
				char ch = str.charAt(j - 1);
 
				if (ch == 'Y')
					arr[i][j] = 1;
 
				else if (i != j)
					arr[i][j] = 1 << 20;
 
			}
		}
		floyd_warshall();
		for (int i = 1; i <= N; i++) {
			int tmp = 0;
			for (int j = 1; j <= N; j++) {
				if (i == j)
					continue;
				else if (arr[i][j] <= 2)
					tmp++;
			}
			result = Math.max(result, tmp);
		}
		System.out.println(result);
	}
 
	public static void floyd_warshall() {
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (i == j || j == k || i == k)
						continue;
					else if (arr[i][j] > arr[i][k] + arr[k][j])
						arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
}

복잡도

시간: O(V³) — 플로이드-워셜 알고리즘 (V = N ≤ 50)
공간: O(V²) — N×N 인접 행렬

문제