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

안녕하세요, 여러분! 이번 포스팅에서는 C++ 알고리즘 문제로 “선물 전달하기”라는 주제를 다뤄보겠습니다. 이 문제는 특히 순차적 사고와 알고리즘 디자인 능력을 시험하는 데 초점이 맞춰져 있습니다.

문제 설명

선물 전달하기 문제는 여러 명이 있는 그룹에서 선물을 상호 간에 전달하는 과정을 모델링했습니다. 여러분은 다음의 조건을 갖춘 문제를 해결해야 합니다.

n명의 사람들이 있습니다.
각 사람은 한 개의 선물을 가집니다.
어떤 두 사람은 서로에게 선물을 전달할 수 있습니다.

여러분의 목표는 모든 사람이 최소한 한 개의 선물을 받도록 선물을 최적으로 전달하는 방법을 찾는 것입니다.

입력 형식

첫 번째 줄에 사람의 수 n이 주어지며, 다음 n개의 줄에는 각 사람이 가지고 있는 선물의 정보가 주어집니다.

출력 형식

모든 사람이 적어도 하나의 선물을 받는 최소한의 선물 전달 방법을 출력합니다.

접근 방법

이번 문제를 해결하기 위해서는 그래프 이론의 기초와 BFS 또는 DFS와 같은 탐색 알고리즘에 대한 이해가 필요합니다. 문제를 해결하기 위한 전략은 다음과 같습니다:

문제를 그래프 형태로 모델링하기
BFS 또는 DFS를 이용하여 선물 전달 경로 탐색하기
각 노드(사람)에서 최소 경로를 찾아 선물 전달하기

C++ 코드 구현

이제 본격적으로 C++ 코드를 통해 문제를 해결해 보겠습니다. 아래 코드는 주어진 조건을 바탕으로 사람들 간의 선물 전달을 구현한 예제입니다.

            
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Person {
    int id;
    vector<int> gifts;
};

// 선물 전달을 위한 선 그래프
void giftExchange(vector<Person> &people) {
    queue<int> q;
    vector<bool> received(people.size(), false);

    // 처음 선물을 받지 못한 사람을 찾아 큐에 넣음
    for (int i = 0; i < people.size(); ++i) {
        if (people[i].gifts.empty()) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int giftRecipient : people[current].gifts) {
            if (!received[giftRecipient]) {
                cout << "사람 " << current << "이(가) 사람 " << giftRecipient << "에게 선물을 전달하였습니다!" << endl;
                received[giftRecipient] = true;
                // 선물을 전달한 후 현재 사람을 다시 큐에 추가
                q.push(giftRecipient);
            }
        }
    }
}

int main() {
    int n;
    cout << "사람의 수를 입력하세요: ";
    cin >> n;
    vector<Person> people(n);

    for (int i = 0; i < n; ++i) {
        people[i].id = i;
        int m;
        cout << "사람 " << i << " 이(가) 주는 선물의 수를 입력하세요: ";
        cin >> m;

        for (int j = 0; j < m; ++j) {
            int giftRecipient;
            cout << "사람 " << i << " 이(가) 전달할 선물 받는 사람의 ID 입력: ";
            cin >> giftRecipient;
            people[i].gifts.push_back(giftRecipient);
        }
    }

    giftExchange(people);
    return 0;
}

코드 설명

위의 코드는 선물 전달 문제를 해결하기 위한 C++ 프로그램을 구현합니다. 각 사람은 자신의 선물 목록을 가지고 있으며, 큐를 사용하여 전달 과정을 시뮬레이션합니다. 선물을 한 번도 받지 못한 사람부터 시작하여, 각 사람이 전달하는 선물을 적절히 시뮬레이션하는 방식입니다.

코드 분석

코드를 차례대로 분석해 보겠습니다:

구조체 정의: struct Person는 사람의 ID와 그 사람이 전달할 선물의 정보를 저장합니다.
큐 초기화: 선물을 받지 못한 사람을 찾아 큐에 추가합니다.
반복문: 큐에서 사람을 하나씩 꺼내고, 해당 사람이 보유한 선물을 전달하는 과정을 진행합니다.

주요 개념 해설

이 문제를 통해 다음과 같은 알고리즘 개념을 이해할 수 있습니다:

BFS 탐색: 너비 먼저 탐색(Breadth-First Search) 알고리즘을 사용하여 선물 전달 과정을 시뮬레이션합니다.
그래프 모델링: 사람과 선물 전달 관계를 그래프 형태로 모델링하여 문제를 효율적으로 해결합니다.

문제 해결 후 생각할 점

문제를 해결한 후, 다음과 같은 질문들을 스스로에게 해보세요:

이 알고리즘의 시간 복잡도는 얼마인가요?
다른 접근 방법이 있었나요?
이 문제를 변형하여 응용해볼 수 있는 다른 문제는 어떤 것들이 있을까요?

결론

코딩테스트 준비에는 다양한 문제를 경험하고 알고리즘 설계 능력을 키우는 것이 중요합니다. “선물 전달하기” 문제를 통해 DFS와 BFS 방식으로 그래프 탐색을 익힐 수 있었기를 바랍니다. C++ 언어의 특징을 잘 활용하여 효율적인 코드를 작성하는 연습도 게을리하지 마세요!

다음 시간에는 또 다른 흥미로운 문제를 가지고 오겠습니다. 감사합니다!