boj-1018-친구

boj_1058_친구

🙋‍♂️들어가며

이번 문제는 이해를 기반으로 한 배열 응용 문제이다

문제

문제

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

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

입력

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

출력

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

풀이

2단계 친구가 되는법

사람 A와 B가 2단계 친구가 되기 위해서는

• A가 B의 친구
• A와 친구이고, B와 친구인 C가 존재할 것

도식으로 나타내면 다음과 같다

A-B

A-C-B

다음 사진은 testcase-4 의 내용이다

10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN

본인을 제외하면 8개가 된다

그렇다면 코드로 보자

boolean[] friend 를 만들어서 각 사람별 친구 인원수를 2단계까지 파악하여 최대값 갱신을 하자

코드

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


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		char[][] arr = new char[N][N];
		for (int r = 0; r < N; r++) {
			arr[r] = br.readLine().toCharArray();
		}
		
		
		int cnt_max = Integer.MIN_VALUE;
		for (int r = 0; r < N; r++) {
			boolean[] friend = new boolean[N];
			int cur_cnt = 0;
			
			// 1단계 친구
			for (int c = 0; c < N; c++) {
				// 동일인물이면 skip
				if (r == c) continue;
				// Y라면 -> 친구
				if (arr[r][c] == 'Y') friend[c] = true;
				
				// 2단계 친구
				for (int d = 0; d < N; d++) {
					if (d != r && arr[r][c] == 'Y' && arr[c][d] == 'Y') friend[d] = true;
				}
			}
			
			// 비교
			for (int k = 0; k < N; k++) {
				if (friend[k] == true) {
					cur_cnt++;
				}
			}
			cnt_max = Math.max(cnt_max, cur_cnt);
		}
		
		
		System.out.println(cnt_max);
		
	}
}

}

제출결과 -> 0.068초