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