[Baekjoon/JAVA] 1058번 - 친구

Baekjoon Online Judge

문제로 이동

 

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 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
3 NNN NNN NNN	0
5 NYNNN YNYNN NYNYN NNYNY NNNYN	4
10 NNNNYNNNNN NNNNYNYYNN NNNYYYNNNN NNYNNNNNNN YYYNNNNNNY NNYNNNNNYN NYNNNNNYNN NYNNNNYNNN NNNNNYNNNN NNNNYNNNNN	8
15 NNNNNNNNNNNNNNY NNNNNNNNNNNNNNN NNNNNNNYNNNNNNN NNNNNNNYNNNNNNY NNNNNNNNNNNNNNY NNNNNNNNYNNNNNN NNNNNNNNNNNNNNN NNYYNNNNNNNNNNN NNNNNYNNNNNYNNN NNNNNNNNNNNNNNY NNNNNNNNNNNNNNN NNNNNNNNYNNNNNN NNNNNNNNNNNNNNN NNNNNNNNNNNNNNN YNNYYNNNNYNNNNN	6

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt(); // 사람의 수 N
        String friend[] = new String[N]; // 각 사람들의 친구 리스트

        // 입력
        for (int i = 0; i < N; i++)
            friend[i] = in.next();

        // 출력
        System.out.println(friendCnt(friend, N));
    }

    // 가장 유명한 사람의 2-친구의 수 찾기
    public static int friendCnt(String[] friend, int N) {
        int f = 0; // 가장 유명한 사람의 2-친구의 수

        for (int i = 0; i < N; i++) {
            boolean check[] = new boolean[N]; // 이미 세아린 친구를 또 세지 않기 위함
            check[i] = true; // 자기 자신을 미리 체크

            int num = 0; // i번째 사람의 친구의 수

            for (int j = 0; j < N; j++) {
                // 서로 친구인 경우 찾기
                if (friend[i].charAt(j) == 'Y' && !check[j]) {
                    check[j] = true;
                    num++;

                    // 한다리 건너서 친구인 사람 찾기
                    for (int k = 0; k < N; k++) {
                        // 마지막 조건은 방문해야 하는데 이미 방문처리되어 방문하지 못하게 되는 것을 막기 위해 추가
                        if (friend[j].charAt(k) == 'Y' && !check[k] && friend[i].charAt(k) != 'Y') {
                            check[k] = true;
                            num++;
                        }
                    }
                }
            }

            // 가장 유명한 사람의 친구 수 저장
            if (num > f) f = num;

            // 한 사람이 가질 수 있는 최대 친구 수는 N - 1이다.
            if (f == N - 1) break;
        }

        return f;
    }
}

가장 유명한 사람의 2 - 친구의 수를 찾는 int friendCnt(string[], int)함수를 만들어서 문제를 풀었다.

 

boolean check[] = new boolean[N]; // 이미 세아린 친구를 또 세지 않기 위함
check[i] = true; // 자기 자신을 미리 체크

int num = 0; // i번째 사람의 친구의 수

for (int j = 0; j < N; j++) {
	// 서로 친구인 경우 찾기
	if (friend[i].charAt(j) == 'Y' && !check[j]) {
		check[j] = true;
		num++;

        // 한다리 건너서 친구인 사람 찾기
        for (int k = 0; k < N; k++) {
			// 마지막 조건은 방문해야 하는데 이미 방문처리되어 방문하지 못하게 되는 것을 막기 위해 추가
			if (friend[j].charAt(k) == 'Y' && !check[k] && friend[i].charAt(k) != 'Y') {
				check[k] = true;
				num++;
			}
		}
	}
}

i번째 사람의 친구 수를 구하는 부분이다. i번째 사람의 친구리스트에서 j번째 사람이 친구라면 j번째 사람의 친구리스트로 넘어가서 한다리 건너서 친구인 사람을 찾게 된다. i와 직접적/ 한다리 건너 친구인 사람은 check[]에 true로 표시되어 이미 세아린 사람은 또 친구 숫자에 포함되지 않게끔 한다.

 

이때 한다리 건너 친구를 모두 check하게 되면 직접적인 친구 리스트 검사로 한다리 건너 친구를 찾지 못하게 되는 경우가 발생한다. 이를 방지하기 위해 i번째 사람과 직접적으로 친구인 사람이라면 한다리 건너 친구 찾기에서 제외하게 했다.