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

문제 설명

당신은 친구 관계를 분석하는 이메일 서비스를 개발하고 있습니다. 사용자 각각은 친구 리스트를 가지고 있으며, 친구는 서로에게 친밀한 관계를 형성합니다. 당신의 작업은 주어진 친구 관계 데이터를 기반으로, 두 사용자가 서로 친구인지를 확인하고, 친구의 친구도 포함하여 이들 사이의 간접적인 친밀도를 계산하는 것입니다.

입력으로는 친구 리스트와 확인할 사용자의 ID가 주어집니다. 친구 리스트는 리스트의 형태로, 각 리스트의 요소는 서로 친구인 사용자 ID의 쌍으로 구성됩니다. 이 정보를 바탕으로 두 사용자가 간접적으로 친구인지 아닌지를 판단하는 프로그램을 작성하세요.

입력 예시

    친구 리스트: [(1, 2), (2, 3), (3, 4), (1, 5)]
    사용자 ID1: 1
    사용자 ID2: 4

출력 예시

    1과 4는 친구이거나 간접 친구입니다.

해결 방법

이 문제를 해결하기 위해서는 그래프의 형태를 사용해야 합니다. 친구 관계를 정점(Vertex)과 엣지(Edge)로 모델링하고 BFS(Breadth-First Search) 또는 DFS(Depth-First Search) 알고리즘을 통해 두 사용자 사이의 관계를 탐색하면 됩니다. 이 과정을 통해 직접 친구와 간접 친구를 확인할 수 있습니다.

1. 그래프 모델링

친구 리스트를 기반으로 무방향 그래프를 생성합니다. 각 사용자는 값으로 사용자의 ID가 사용되며, 친구 관계는 두 사용자 간의 엣지로 표현됩니다.

2. BFS 또는 DFS 구현

이제 그래프가 만들어졌다면, BFS 또는 DFS를 통해 주어진 두 사용자의 간접 친구 관계를 찾습니다. 이 과정에서 방문한 노드를 기록하고 이미 방문한 노드라면 탐색을 중단합니다.

3. 코드 예시


using System;
using System.Collections.Generic;

class FriendNetwork
{
    private Dictionary> graph = new Dictionary>();

    public void AddFriendship(int user1, int user2)
    {
        if (!graph.ContainsKey(user1))
            graph[user1] = new List();
        if (!graph.ContainsKey(user2))
            graph[user2] = new List();

        graph[user1].Add(user2);
        graph[user2].Add(user1);
    }

    public bool AreFriends(int user1, int user2)
    {
        if (user1 == user2) return true;
        HashSet visited = new HashSet();
        Queue queue = new Queue();
        
        queue.Enqueue(user1);
        visited.Add(user1);

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            foreach (var friend in graph[current])
            {
                if (friend == user2)
                    return true;

                if (!visited.Contains(friend))
                {
                    visited.Add(friend);
                    queue.Enqueue(friend);
                }
            }
        }
        return false;
    }
}

class Program
{
    static void Main(string[] args)
    {
        FriendNetwork network = new FriendNetwork();
        
        // 친구 관계 추가
        network.AddFriendship(1, 2);
        network.AddFriendship(2, 3);
        network.AddFriendship(3, 4);
        network.AddFriendship(1, 5);

        // 두 사용자 간의 관계 확인
        int user1 = 1;
        int user2 = 4;

        if (network.AreFriends(user1, user2))
            Console.WriteLine($"{user1}과 {user2}는 친구이거나 간접 친구입니다.");
        else
            Console.WriteLine($"{user1}과 {user2}는 친구가 아닙니다.");
    }
}

4. 코드 설명

위 코드는 친구 관계를 관리하고, 두 사용자가 친구인지 확인하는 방법을 보여줍니다. FriendNetwork 클래스는 친구 목록을 저장하는 그래프와 친구 관계 추가를 위한 메서드를 제공합니다. AreFriends 메서드는 BFS를 사용하여 두 사용자 간의 연결성을 확인합니다.

5. 복잡도 분석

그래프의 인접 리스트를 사용한 이 구현의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 엣지의 수입니다. 공간 복잡도 또한 O(V + E)입니다.

결론

이와 같이 친구 관계 문제를 해결하기 위해 그래프와 탐색 알고리즘을 적절히 활용할 수 있습니다. C#에서는 다양한 자료结构와 알고리즘을 통해 이런 문제를 우아하게 해결할 수 있으며, 이를 통해 취업 면접 및 코딩 테스트에서 강력한 문제 해결 능력을 보여줄 수 있습니다.