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

본 글에서는 C++을 활용하여 친구 관계를 파악하는 알고리즘 문제를 해결하는 과정을 다루어 보겠습니다. 이 문제는 친구의 수와 관계를 기반으로 그래프 이론을 적용하여 친구 관계를 파악하는 것입니다. 이와 관련하여 자료구조 및 알고리즘의 기본 개념을 이해하고, C++에서의 구현 방법을 자세히 살펴보겠습니다.

문제 설명

문제: N명의 학생이 있습니다. 각 학생은 친구가 될 수 있는 관계를 가집니다. 친구의 관계는 양방향이며, 친구 관계가 주어졌을 때, 특정 학생이 몇 명의 친구를 가지고 있는지를 파악하는 알고리즘을 구현하세요. 또한, 두 명의 학생이 서로 친구인지 여부를 확인할 수 있어야 합니다.

입력:

첫 번째 줄에 학생의 수 N (1 ≤ N ≤ 1000)가 주어진다.
두 번째 줄에 M (0 ≤ M ≤ N*(N-1)/2)개의 친구 관계가 주어진다.
각 친구 관계는 A와 B를 포함하며, A는 B의 친구이고, B는 A의 친구이다.
마지막으로 친구 관계를 확인하고자 하는 쿼리가 주어진다.

문제 풀이 과정

문제를 해결하기 위해 다음의 단계를 거치겠습니다:

그래프 모델링: 친구 관계를 그래프로 모델링합니다. 정점(vertex)은 학생을 나타내고, 간선(edge)은 친구 관계를 나타냅니다.
인접 리스트 구성: 각 정점에 대해 친구를 나타내는 인접 리스트를 구성합니다.
친구 수 계산: 특정 학생의 친구 수를 계산하는 함수를 구현합니다.
친구 관계 확인: 두 학생의 친구 관계를 확인하는 함수를 구현합니다.

1. 그래프 모델링

주어진 문제를 해결하기 위해서는 먼저 친구 관계를 그래프 형태로 모델링해야 합니다. 이 경우 그래프의 정점은 학생을 나타내며, 간선은 그 학생 간의 친구 관계를 나타냅니다.

따라서, N명의 학생이 있다고 가정할 때, 이를 0부터 N-1까지의 정수로 표현할 수 있습니다. 예를 들어, 학생 A는 0, 학생 B는 1로 나타낼 수 있습니다.

2. 인접 리스트 구성

그래프를 표현하기 위해 인접 리스트를 사용합니다. 각 학생을 키(key)로 하고, 그 학생과 친구인 학생들의 목록을 값(value)으로 가지는 해시맵이나 벡터를 사용할 수 있습니다. 다음은 C++ 언어로 인접 리스트를 구성하는 방법입니다:


#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

unordered_map> friends;

void addFriendship(int a, int b) {
    // 친구관계 추가 (양방향)
    friends[a].push_back(b);
    friends[b].push_back(a);
}

위의 코드에서 addFriendship 함수는 두 학생 간의 친구 관계를 추가합니다.

3. 친구 수 계산

특정 학생의 친구 수를 계산하기 위해, 해당 학생의 인접 리스트의 크기를 반환하는 함수를 구현합니다. 아래는 그 구현 예시입니다:


int countFriends(int student) {
    return friends[student].size();
}

이 코드는 인접 리스트에서 특정 학생의 친구 목록의 크기를 반환합니다.

4. 친구 관계 확인

두 학생이 친구인지 여부를 확인하는 함수도 필요합니다. 이 함수는 인접 리스트를 검색하여 두 학생이 동일한 친구 리스트에 있는지를 확인합니다. 아래는 그 구현 예시입니다:


bool areFriends(int a, int b) {
    // A의 친구 목록을 가져온다
    for (int friend_id : friends[a]) {
        if (friend_id == b) {
            return true; // 친구 관계가 존재함
        }
    }
    return false; // 친구 관계가 존재하지 않음
}

위의 함수는 학생 A의 친구 목록을 순회하여 학생 B가 친구인지 확인합니다.

전체 코드

이제까지 설명한 내용을 종합하여 완전한 코드를 작성하겠습니다:


#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map> friends;

void addFriendship(int a, int b) {
    friends[a].push_back(b);
    friends[b].push_back(a);
}

int countFriends(int student) {
    return friends[student].size();
}

bool areFriends(int a, int b) {
    for (int friend_id : friends[a]) {
        if (friend_id == b) {
            return true;
        }
    }
    return false;
}

int main() {
    int N, M;
    cout << "학생 수 (N)와 친구 관계 수 (M)를 입력하세요: ";
    cin >> N >> M;

    cout << "친구 관계를 입력하세요 (예: A B): " << endl;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        addFriendship(a, b);
    }

    int query;
    cout << "친구 수를 확인할 학생의 번호를 입력하세요: ";
    cin >> query;
    cout << "학생 " << query << "의 친구 수: " << countFriends(query) << endl;

    int a, b;
    cout << "친구 관계를 확인할 두 학생의 번호를 입력하세요: ";
    cin >> a >> b;
    if (areFriends(a, b)) {
        cout << "학생 " << a << "와 학생 " << b << "는 친구입니다." << endl;
    } else {
        cout << "학생 " << a << "와 학생 " << b << "는 친구가 아닙니다." << endl;
    }

    return 0;
}

결론

본 강좌에서는 친구 관계를 파악하는 알고리즘 문제를 C++ 언어로 해결하는 과정을 자세히 살펴보았습니다. 그래프 이론과 자료구조의 중요한 개념들을 활용하여 친구 관계를 모델링하고, 이를 통해 문제를 해결하는 방법을 배울 수 있었습니다. 이와 같은 알고리즘 문제 해결 능력은 취업을 위한 코딩 테스트에서 매우 중요하므로, 다양한 문제를 통해 실력을 다져 나가시기를 바랍니다.