[Algorithm] 백준 1058 - 최단경로 / 친구

백준 실버 ~ 골드 문제를 풀며 정리한 내용입니다.

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

 

문제

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

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

 

 

입력

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

 

출력

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

 

- 예제 입력

3
NYY
YNY
YYN

 

- 예제 출력

2

 

 

📌 풀이

플로이드 와샬 알고리즘을 이용해 풀었다.

모든 경우의 수에서 갈 수 있는 모든 경우의 수의 최대를 구해야 하는 문제이기 때문에 해당 알고리즘 사용을 결정했다.

 

입력받은 경우의 수 만큼 각각 i와 j간의 관계(친구인지 아닌지)를 저장할 이차원 배열과 친구 여부를 저장할 불리언 배열을 만들어 주었다. 반복문을 돌면서 주어진 값이 친구인지 아닌지를 판단해 불리언 배열의 값을 true로 저장한다. 이때 i와 j의 사이의 임의의 경로를 1번 거쳐서 연결되어도 2친구에 해당하기 때문에 그 요소를 확인해준다. 

 

이후 불리언 배열의 친구 여부에 따라 2친구 변수의 수를 ++ 해주고 최댓값을 찾아 비교해 저장해준 뒤 반복문이 종료되면 출력해준다.

 

플로이드 와샬 알고리즘만 알고 있다면 간단히 풀 수 있을 것 같다. 주의해야 할 점은 친구 여부를 판단할 때, 3친구 이상이 되면 안된다는 점 이다. 직접 친구 또는 2친구(사이의 경로 딱 1개) 까지만 가능하다.

 

구현

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());

		char[][] friend = new char[N][N];
		boolean[][] isFriend = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				friend[i][j] = str.charAt(j);
			}
		}

		int max = Integer.MIN_VALUE;
		
		for (int i = 0; i < N; i++) {
			int twoFriend = 0;
			for (int j = 0; j < N; j++) {
				if(friend[i][j]=='Y') {
					isFriend[i][j] = true;
					for (int k = 0; k < N; k++) {
						if(friend[j][k]=='Y') isFriend[i][k] = true;
					}
				}
			}
			
			for (int j = 0; j < N; j++) {
				if(i==j) continue;
				if(isFriend[i][j]) twoFriend++;
			}
			 
			max = Math.max(max, twoFriend);
		}
		
		System.out.println(max);

	}

}