[백준] 친구 (1058번)

N명의 사람들이 친구 관계를 나타내는 그래프를 바탕으로, 특정 사람의 "2-친구"(직접 친구거나 친구의 친구인 관계)를 계산한 뒤, 가장 많은 2-친구를 가진 사람의 수를 출력합니다.

 

코드 힌트

1. 입력 처리
   • 사람 수 N과 N×N 크기의 친구 관계를 나타내는 그래프를 입력받습니다.
   • 그래프는 각 사람이 다른 사람과 친구인지 여부를 "Y"(친구)와 "N"(친구 아님)으로 나타냅니다.
2. 최대 2-친구 탐색
   • 각 사람을 시작점으로 하여, "2-친구"를 탐색합니다.
   • 이를 위해 너비 우선 탐색(BFS)를 사용합니다:
     • 시작점에서 직접 친구(깊이 1)와 친구의 친구(깊이 2)까지만 탐색합니다.
     • 이미 방문한 사람은 중복 처리하지 않습니다.
3. 결과 계산
   • 각각의 사람에 대해 계산된 2-친구 수를 확인하고, 가장 큰 값을 갱신합니다.
   • 마지막에 가장 많은 2-친구를 가진 사람의 수를 출력합니다.

 

탐색 방식

• 탐색은 BFS(너비 우선 탐색) 알고리즘을 사용하여 이루어집니다.
  • BFS는 큐(Queue)를 사용해 각 단계에서 탐색할 노드(사람)를 순차적으로 처리합니다.
  • 이때, 각 사람의 탐색 깊이를 관리하여 "2-친구"까지만 포함되도록 제한합니다.
• 탐색 중:
  • 직접 친구(1단계)와 친구의 친구(2단계)를 차례로 확인합니다.
  • 이미 방문한 사람은 중복 탐색하지 않습니다.

 

 

핵심 고려 사항

• 그래프 표현: N×N 배열은 각 사람 간의 친구 관계를 나타냅니다.
• 탐색 제한: 탐색 깊이를 2로 제한하여 2-친구만 계산합니다.
• 최대값 갱신: 모든 사람에 대해 탐색한 결과 중 최대값을 출력합니다.

 

---

정답은 더보기 클릭

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

public class Main {

    static String[][] graph; // 친구 관계를 나타내는 그래프 (N x N 크기의 배열)
    static int N; // 사람 수
    static int max = -1; // 최대 2-친구 수를 저장하는 변수

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

        // 입력: 사람 수
        N = in.nextInt();
        in.nextLine(); // 개행 문자 제거

        // 입력: 친구 관계 그래프
        graph = new String[N][N];
        for (int i = 0; i < N; i++) {
            graph[i] = in.nextLine().split(""); // 각 줄을 문자열 배열로 저장
        }

        // 각 사람에 대해 2-친구 탐색
        for (int i = 0; i < N; i++) {
            max = Math.max(max, bfs(i)); // 최대 2-친구 수 갱신
        }

        // 출력: 최대 2-친구 수
        System.out.println(max);
    }

    // BFS를 사용해 특정 사람의 2-친구 수를 계산하는 메서드
    public static int bfs(int start) {
        Queue<int[]> queue = new LinkedList<>(); // BFS 탐색을 위한 큐
        queue.add(new int[]{start, 0}); // 시작 노드와 깊이(0)를 큐에 추가

        boolean[] visit = new boolean[N]; // 방문 여부를 저장하는 배열
        visit[start] = true; // 시작 노드는 방문 처리

        int count = 0; // 2-친구 수를 저장하는 변수

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll(); // 큐에서 현재 노드와 깊이를 가져옴
            int idx = tmp[0]; // 현재 노드
            int depth = tmp[1]; // 현재 깊이

            // 탐색 깊이가 2 이상이면 더 이상 진행하지 않음
            if (depth >= 2) {
                continue;
            }

            // 현재 노드와 연결된 노드 탐색
            for (int i = 0; i < N; i++) {
                // 친구 관계가 있고 아직 방문하지 않은 노드라면
                if (graph[idx][i].equals("Y") && !visit[i]) {
                    count++; // 2-친구 수 증가
                    visit[i] = true; // 방문 처리
                    queue.add(new int[]{i, depth + 1}); // 다음 깊이로 큐에 추가
                }
            }
        }

        return count; // 계산된 2-친구 수 반환
    }
}