C# 코딩테스트 강좌, 선물 전달하기

문제 설명

당신은 친구들에게 크리스마스 서프라이즈 선물을 전달하는 이벤트를 기획하고 있습니다.
N명의 친구가 있고 각 친구는 선물을 받고 싶은 목록을 가지고 있습니다.
당신은 가능한 한 많은 친구들이 원하는 선물을 받을 수 있도록 해야 합니다.
각 친구는 원하는 선물 한 가지를 지정하며, 선물은 하나 밖에 없습니다.
단, 선물은 하나의 친구에게만 전달될 수 있습니다.

입력 형식

첫째 줄에 친구의 수 N이 주어집니다.
둘째 줄부터 N번째 줄까지 각 친구가 원하는 선물이 나열됩니다.

출력 형식

최대 몇 명의 친구들이 원하는 선물을 받을 수 있는지 출력합니다.

제한

1 ≤ N ≤ 100
선물은 알파벳 대문자로 표기되며, 최대 26종류가 존재합니다.

문제 접근 방법

이 문제는 기본적으로 그래프 이론에서 최대 매칭 문제와 유사합니다.
각 친구를 정점으로, 친구가 원하는 선물을 간선으로 연결할 수 있습니다.
이 문제를 해결하기 위해 우리는 친구들의 선물 요청을 입력 받아
각 선물에 대해 친구가 요청한 목록을 생성한 뒤,
최대 매칭을 구하는 알고리즘을 사용할 것입니다.

알고리즘 개요

– 입력된 친구의 수와 요청된 선물을 기반으로 그래프를 구성합니다.
– 그래프를 탐색하여 각 친구에게 할당 가능한 선물을 찾습니다.
– DFS(Depth First Search) 알고리즘을 사용하여 가능한 매칭을 시도합니다.

코드 구현

아래는 C#으로 작성된 선물 전달하기 문제의 풀이 코드입니다.

                
using System;
using System.Collections.Generic;

class Program
{
    static int N;                         // 친구의 수
    static List friends;          // 친구가 원하는 선물 목록
    static Dictionary gifts; // 각 선물의 매칭 상태
    static bool[] visited;                // DFS 방문 여부 기록

    static void Main(string[] args)
    {
        N = int.Parse(Console.ReadLine());
        friends = new List();

        for (int i = 0; i < N; i++)
        {
            friends.Add(Console.ReadLine());
        }

        gifts = new Dictionary();
        int totalMatched = 0;

        foreach (var friend in friends)
        {
            visited = new bool[26];
            if (DFS(friend[0], ref totalMatched))
            {
                totalMatched++;
            }
        }

        Console.WriteLine(totalMatched);
    }

    static bool DFS(char gift, ref int totalMatched)
    {
        int index = gift - 'A';

        if (visited[index]) return false; // 이미 방문한 선물
        visited[index] = true;

        if (!gifts.ContainsKey(gift.ToString()) || gifts[gift.ToString()] == -1)
        {
            gifts[gift.ToString()] = totalMatched; // 선물 매칭
            return true;
        }

        return false;
    }
}

코드 설명

위 코드는 다음과 같은 절차로 선물 전달 문제를 해결합니다.

입력 읽기: 친구의 수 N을 입력받고, 각 친구마다 원하는 선물을 입력받습니다.
DFS 함수 구현: 요청한 선물이 가능한지 확인하며, 매칭을 시도합니다.
방문 여부 기록: 선물 당 한 번만 요청을 수용하기 위해 방문 기록을 관리합니다.
결과 출력: 최대 매칭 결과를 출력합니다.

시간 복잡도

이 알고리즘은 O(N^2) 복잡도를 가집니다.
각 친구에 대해 DFS를 호출하고, 선물의 수는 최대 26개로 제한되어 있기 때문에
문제의 범위 안에서는 충분히 효율적입니다.

결론

“선물 전달하기” 문제는 친구들에게 선물을 배분하는 흥미로운 문제입니다.
DFS와 그래프의 최대 매칭 원리를 통해 구현할 수 있음을 보여주었습니다.
향후 비슷한 문제에서도 이 원리를 적용하여 풀이할 수 있을 것입니다.

이 글이 C# 코딩 테스트 대비에 도움이 되었으면 합니다.
다양한 문제를 통해 알고리즘을 연습해 보시기 바랍니다.