안녕하세요. 오늘은 자바를 활용한 코딩 테스팅 강좌를 통해 불우이웃돕기와 관련된 알고리즘 문제를 다루어보겠습니다. 불우이웃돕기란, 도움이 필요한 이웃을 위해 지원하는 활동을 뜻합니다. 이 문제를 통해 우리는 ‘배정하기’라는 알고리즘을 이해하고 구현해 보겠습니다.
문제 설명
가산호, 성훈, 민재 3명의 자원봉사자는 각각 정해진 시간에 따라 불우이웃에게 도움을 주기로 했습니다. 하지만 각 자원봉사자는 혼자서 모든 불우이웃에게 도움을 줄 수는 없기 때문에, 시간을 효율적으로 배분해야 합니다.
아래의 조건들을 고려하여, 불우이웃들에게 가장 많은 도움을 줄 수 있는 자원봉사자들을 배정하는 알고리즘을 구현하시오:
- 자원봉사자의 수: N (1 ≤ N ≤ 100)
- 불우이웃의 수: M (1 ≤ M ≤ 100)
- 각 자원봉사자는 최대 K명의 불우이웃에게 도움을 줄 수 있다.
- 자원봉사자와 불우이웃 간의 연결을 나타내는 인접 행렬은 주어진다.
입력 형식
첫 번째 줄에는 자원봉사자의 수 N과 불우이웃의 수 M이 주어집니다. 이후 N개의 줄에 걸쳐 각 자원봉사자가 도울 수 있는 불우이웃의 정보가 주어집니다. 1은 도울 수 있다는 의미이며, 0은 도울 수 없다는 의미입니다.
출력 형식
가장 많은 불우이웃에게 도움을 준 자원봉사자의 수와 그들 각각이 도울 수 있는 불우이웃의 번호를 출력합니다.
예제 입력
3 4
1 1 0 1
1 0 1 1
0 1 1 0
예제 출력
2
1 2
2 3
문제 풀이 과정
이 문제를 해결하기 위해서 우리는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)와 같은 탐색 기법을 활용할 수 있습니다. 배정 문제를 해결하기 위한 알고리즘을 설계하기 위해 다음의 과정을 따르도록 합니다:
1단계: 입력 데이터 처리하기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 자원봉사자 수
int M = sc.nextInt(); // 불우이웃 수
int[][] graph = new int[N][M]; // 인접 행렬 생성
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
graph[i][j] = sc.nextInt(); // 인접 행렬 입력
}
}
2단계: 자원봉사자 배정하기
자원봉사자가 각 불우이웃에게 도움을 줄 수 있는 상황을 바탕으로 DFS를 활용하여 가능한 모든 조합을 탐색합니다:
boolean[] visited = new boolean[M]; // 방문 여부 체크
int[] result = new int[N]; // 결과 배열
int[] assignment = new int[N]; // 자원봉사자 할당
for (int i = 0; i < N; i++) {
Arrays.fill(visited, false); // 방문 배열 초기화
assignVolunteerToNeighbour(i, graph, visited, assignment);
}
private static boolean assignVolunteerToNeighbour(int volunteer, int[][] graph, boolean[] visited, int[] assignment) {
for (int neighbour = 0; neighbour < M; neighbour++) {
if (graph[volunteer][neighbour] == 1 && !visited[neighbour]) {
visited[neighbour] = true;
if (assignment[neighbour] == -1 || assignVolunteerToNeighbour(assignment[neighbour], graph, visited, assignment)) {
assignment[neighbour] = volunteer;
return true;
}
}
}
return false;
}
3단계: 최종 결과 출력하기
for (int i = 0; i < N; i++) {
if (assignment[i] != -1) {
System.out.println((assignment[i] + 1) + " " + (i + 1));
}
}
결론
오늘은 불우이웃돕기와 관련된 자바 코딩 테스트 문제를 통해 자원봉사자를 배정하는 알고리즘을 구현해 보았습니다. 이 문제를 통해 그래프 이론과 탐색 알고리즘에 대해 더 깊이 이해할 수 있었으면 좋겠습니다. 또한, 코딩테스트와 실무에서 직접적으로 활용할 수 있는 기술을 연습하는 데 도움이 되었기를 바랍니다. 다음 강좌에서도 새로운 알고리즘 문제를 가지고 돌아오겠습니다. 감사합니다!