자바 코딩테스트 강좌, 친구 관계 파악하기

안녕하세요, 여러분! 이번 포스트에서는 코딩테스트에서 자주 등장하는 친구 관계 파악하기 문제를 다뤄보겠습니다. 소개할 문제는 그래프 탐색 문제이며, 친구 관계를 분석하여 특정 조건을 만족하는 친구의 수를 계산하는 과제를 제시합니다.

문제 설명

여러분은 N명의 친구가 있는 파티를 주최했습니다. 각 친구는 서로에게 친구 관계로 연결되어 있습니다. 친구 관계는 양방향이며, 각 친구A와 친구B는 친구들에서만 서로의 친구를 확인할 수 있습니다. 즉, 친구 A의 친구는 A와 직접적으로 연결된 친구뿐입니다. 당신의 임무는 특정 친구의 친구들 중에서 ‘2단계 친구’를 얼마나 찾을 수 있는지 세는 것입니다.

문제 정의

    입력:
    - N (1 ≤ N ≤ 100) : 친구의 수
    - M (1 ≤ M ≤ 10^4) : 친구 관계의 쌍 수
    - M개의 쌍 (A, B): 두 친구 A와 B.

    출력:
    - X: 특정 친구의 2단계 친구의 수.

    특정 친구를 K라고 할 때, K의 2단계 친구를 세는 것입니다.

입력 예시

    6 5
    1 2
    2 3
    1 4
    4 5
    5 6
    1

출력 예시

    2

문제 접근법

이 문제를 해결하기 위해서는 그래프 자료구조를 사용하여 친구 관계를 표현해야 합니다. 이를 위해 인접 리스트(Adjacency List)를 생성하겠습니다. 이후 너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)을 통해 2단계 친구를 찾아야 합니다. 그래프의 각 친구는 정점, 친구 관계는 간선으로 볼 수 있습니다.

단계별 접근법

  1. 입력값을 읽어들이고 친구 관계의 연결 정보를 바탕으로 인접 리스트를 생성합니다.
  2. 특정 친구 K를 기준으로 BFS 또는 DFS를 사용하여 친구의 친구 관계를 탐색합니다.
  3. 탐색 과정 중 K와 직접 연결된 친구는 제외하고, 친구의 친구는 집합(Set)을 사용하여 중복을 방지합니다.
  4. 최종적으로 집합의 크기를 출력합니다.

구현 코드 (Java)

    import java.util.*;

    public class FriendRelations {
        static List[] graph;
        static Set friendsOfFriends;

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            graph = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                graph[i] = new ArrayList<>();
            }

            for (int i = 0; i < M; i++) {
                int A = scanner.nextInt();
                int B = scanner.nextInt();
                graph[A].add(B);
                graph[B].add(A);
            }

            int K = scanner.nextInt();
            friendsOfFriends = new HashSet<>();

            for (int friend : graph[K]) {
                for (int f2 : graph[friend]) {
                    if (f2 != K && !graph[K].contains(f2)) {
                        friendsOfFriends.add(f2);
                    }
                }
            }
            System.out.println(friendsOfFriends.size());
            scanner.close();
        }
    }

코드 설명

코드의 첫 부분에서 친구 관계를 저장할 그래프를 정의하고 입력값을 통해 친구들의 관계를 인접 리스트 형식으로 초기화합니다. 이후 지정한 친구 K를 기준으로 그 친구의 친구들을 탐색하고, 이를 집합에 추가하여 중복을 제거합니다. 마지막으로 집합의 크기를 통해 K의 2단계 친구 수를 구합니다.

코드 실행

이제 코드를 실행하여 결과를 확인해 봅시다. 위의 입력 예시를 사용할 경우 코드의 결과는 ‘2’가 될 것입니다. 이는 특정 친구 K가 총 2명의 2단계 친구를 가진다는 것을 의미합니다.

마무리

이 문제는 그래프 이론의 기초적인 개념을 활용하는 좋은 연습이 됩니다. 친구 관계와 같은 이론은 많은 코딩 인터뷰에서 자주 등장하며, 따라서 이러한 문제를 풀면서 그래프 탐색과 관련된 지식을 더욱 강화할 수 있습니다.

다음 포스트에서도 유익한 알고리즘 문제와 그 풀이 과정을 다루도록 하겠습니다. 궁금한 사항이 있다면 댓글로 남겨주세요!