코딩 테스트를 준비하는 과정에서 여러 알고리즘 문제를 접하게 됩니다. 이번 강좌에서는 ‘선물 전달하기’라는 주제를 가지고 문제를 이해하고 해결하는 과정을 자세히 살펴보겠습니다. 이 문제는 그래프 탐색 및 분배 문제의 복합적인 요소를 가지고 있어, 코딩 테스트에서 자주 등장하는 유형입니다.
문제 설명
어느 날, N명의 친구들이 모여 서로에게 선물을 주기로 했습니다. 친구들은 특정한 규칙에 따라 선물을 주는데, 각 친구는 자신이 선물을 줄 수 있는 친구의 목록을 가지고 있습니다. 선물을 주는 방향과 수는 정해져 있으며, 모든 친구는 반드시 하나의 선물을 받아야 합니다.
우리의 목표는 가능한 모든 경우의 수를 계산하여, 친구들이 서로에게 선물을 주고받는 방법의 총 가짓수를 구하는 것입니다. 문제의 입력은 친구의 수 N과 각 친구가 선물을 줄 수 있는 친구의 인덱스 목록으로 주어집니다.
문제 예시
입력:
4
1 2
2 3
3 4
4 1
출력:
4
위의 예시에서 4명의 친구가 상호적으로 선물을 주고받는 경우의 수는 4가지입니다. 이러한 경우를 찾아내는 것이 우리의 주요 목표입니다.
알고리즘 설계
이 문제를 해결하기 위해서는 그래프 이론을 활용하는 것이 효율적입니다. 친구들을 정점으로 보고, 선물을 줄 수 있는 관계를 간선으로 나타내면 이 문제는 방향 그래프의 형태로 변환됩니다. 이제 이 그래프에서 강한 연결 요소를 찾아야 합니다. 이를 통해 모든 친구가 선물을 주고받을 수 있도록 하는 방법의 수를 계산할 수 있습니다.
우리가 사용할 알고리즘은 다음과 같습니다:
- 그래프를 구성한다.
- 강한 연결 요소(Strongly Connected Components)를 찾는다.
- 각 연결 요소에서 가능한 모든 선물 전달 방법의 수를 계산한다.
- 각 연결 요소의 방법 수를 곱하여 최종 답을 도출한다.
구현
이제 자바를 사용하여 이 알고리즘을 구현해봅시다. 다음은 그 코드입니다:
import java.util.*;
public class GiftDistribution {
static int N;
static List> graph = new ArrayList<>();
static boolean[] visited;
static Stack stack = new Stack<>();
static List> scc = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력 받기
N = sc.nextInt();
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
int count = sc.nextInt();
for (int j = 0; j < count; j++) {
graph.get(i).add(sc.nextInt() - 1);
}
}
visited = new boolean[N];
// 그래프의 모든 정점에 대해 DFS 수행
for (int i = 0; i < N; i++) {
if (!visited[i]) {
dfs(i);
}
}
// 전이 그래프 생성
List> reverseGraph = new ArrayList<>();
for (int i = 0; i < N; i++) {
reverseGraph.add(new ArrayList<>());
}
for (int i = 0; i < N; i++) {
for (int neighbor : graph.get(i)) {
reverseGraph.get(neighbor).add(i);
}
}
Arrays.fill(visited, false);
// SCC 찾기
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
List component = new ArrayList<>();
reverseDfs(v, component, reverseGraph);
scc.add(component);
}
}
// 경우의 수 계산
int result = 1;
for (List component : scc) {
result *= factorial(component.size());
}
System.out.println(result);
}
static void dfs(int v) {
visited[v] = true;
for (int neighbor : graph.get(v)) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
stack.push(v);
}
static void reverseDfs(int v, List component, List> reverseGraph) {
visited[v] = true;
component.add(v);
for (int neighbor : reverseGraph.get(v)) {
if (!visited[neighbor]) {
reverseDfs(neighbor, component, reverseGraph);
}
}
}
static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
}
코드 설명
코드는 다음과 같은 과정으로 이루어져 있습니다:
- 그래프의 입력 처리: 각 친구가 줄 수 있는 친구의 목록을 입력 받아 그래프를 구성합니다.
- DFS를 이용한 스택 생성: 모든 정점에 대해 깊이 우선 탐색을 수행하고, 방문 후 스택에 추가합니다.
- 전이 그래프 만들기: 원래 그래프의 간선을 반대로 하여 전이 그래프를 생성합니다.
- SCC 찾기: 스택에서 정점을 하나씩 꺼내고, 전이 그래프를 통해 SCC를 찾습니다.
- 경우의 수 계산: 각 SCC의 크기에 대한 팩토리얼을 계산하여 최종 결과를 도출합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 O(N + E)입니다. 여기서 N은 노드의 수, E는 간선의 수를 의미합니다. 또한, 공간 복잡도 또한 O(N + E)로, 그래프를 저장하기 위한 공간이 필요합니다.
마무리
이번 강좌를 통해 ‘선물 전달하기’ 문제를 해결하는 방법을 알아보았습니다. 알고리즘의 구현 과정과 복잡도 분석까지 자세히 살펴보았습니다. 이러한 문제는 코딩 테스트뿐만 아니라 실제 프로젝트에서도 종종 마주칠 수 있기 때문에, 그래프 이론 및 알고리즘에 대한 이해를 깊이 하는 것이 중요합니다.
여기서 다룬 내용을 바탕으로 연습문제를 풀어보며 실력을 쌓아보시기 바랍니다. 다음 강좌에서는 또 다른 알찬 문제로 찾아뵙겠습니다!