1번
int fun1(int x, int y)
{
if (x > y)
return 0; // x가 y보다 크면 재귀 종료
return y + fun1(x, y - 1); // y를 더하면서 y-1로 재귀 호출
}기본 종료 조건
- if (x > y) 조건을 만족하면 0을 반환하면서 재귀를 종료합니다.
재귀 호출
- return y + fun1(x, y - 1);
- y를 결과에 더하고, y-1을 인자로 넘겨서 재귀 호출을 합니다.
- 즉, y, y-1, y-2, ..., x까지 모두 더하는 방식입니다.
x부터 y까지의 정수 합을 계산하는 것입니다.
2번
/* Assume that n>=1 */
int fun2(int n)
{
if (n == 1)
return 0;
else
return 1 + fun2(n / 2);
}정수 n이 1이 될 때까지 2로 나누는 횟수를 꼐산하는 함수입니다.
log(n)의 내림값이 될 것입니다.
3번
void fun3(int n)
{
if (n == 0)
return;
fun3(n / 2);
printf("%d", n % 2);
}기본 종료 조건
- if (n == 0) return;
- n이 0이면 재귀를 멈춥니다.
재귀 호출
- fun3(n / 2);
- n을 2로 나눈 몫을 인자로 넘겨서 재귀 호출합니다.
출력
- printf("%d", n % 2);
- n을 2로 나눈 나머지(즉, 2진수의 각 자리 값)를 출력합니다.
이 함수 fun3(n)는 정수 n을 2진수로 변환하여 출력하는 함수입니다.
4번
void fun4(char str[], int start, int end)
{
if (start >= end)
return;
else
{
char temp = str[start];
str[start] = str[end];
str[end] = temp;
fun4(str, start + 1, end - 1);
}
}start가 end보다 크거나 같아지면 교환할 문자가 없으니 종료합니다.
start번째 문자와 end번째 문자와 바꿉니다.
즉, 문자열이 뒤집혀서 "hello"를 넣으면 "olleh"가 됩니다.
5번
int fun(int x, int y)
{
if (y == 0)
return 0;
return (x + fun(x, y - 1));
}a X B 로 표현됩니다.
6번
int fun6(int a[], int n)
{
if (n == 1)
return a[0]; // 배열의 크기가 1이면 첫 번째 요소 반환
int x = fun6(a, n - 1); // 배열의 첫 (n-1)개 요소에서 최댓값 찾기
return (x > a[n - 1] ? x : a[n - 1]); // `x`와 `a[n-1]` 중 큰 값을 반환
}n-1요소에서 최대값을 찾은 후 n번째 요소와 비교 즉 n개의 요소 중 가장 큰 값을 찾습니다.
7번
double fun7(double a[], int n)
{
if (n == 1)
return a[0];
else
return (a[n - 1] + (n - 1) * fun7(a, n - 1)) / n;배열의 n-1개의 원소를 구한 후, n번째 요소에 새로운 평균을 계산합니다. 즉 배열의 마지막 원소를 추가하면서 점진적으로 평균을 계산하는 방식입니다.
8번
int fun8(int a, int b)
{
if (b == 0)
return 1;
if (b % 2 == 0)
return fun8(a * a, b / 2);
return fun8(a * a, b / 2) * a;
}동작 예시
fun8(a, b)가 어떻게 작동하는지 살펴보자.
예시 1: fun8(2, 4)
- b = 4일 때, b는 짝수여서 (a^2)^(b/2)로 바꾼다.
- fun8(2, 4)는 fun8(4, 2)로 바뀌고,
- fun8(4, 2)는 fun8(16, 1)로 바뀌고,
- fun8(16, 1)은 16 * 1을 반환하여 최종적으로 16을 반환.
예시 2: fun8(2, 5)
- b = 5일 때, b는 홀수여서 a * (a^2)^(b/2)로 바꾼다.
- fun8(2, 5)는 fun8(4, 2) * 2로 바뀌고,
- fun8(4, 2)는 fun8(16, 1)로 바뀌고,
- fun8(16, 1)은 16 * 1을 반환하여 16이 되며,
- 결국 fun8(2, 5)는 16 * 2 = 32를 반환.
결과
- fun8(a, b)는 a^b를 빠르게 계산하는 함수로, 분할 정복을 통해 계산을 효율적으로 처리한다.
- 시간 복잡도는 O(log b)로, 일반적인 a^b 계산 방식보다 훨씬 효율적이다.
핵심
- 짝수일 경우: fun8(a * a, b / 2)
- 홀수일 경우: fun8(a * a, b / 2) * a
- b == 0이면 1을 반환.
이 함수는 지수 연산을 효율적으로 처리
log b입니다.
9번
+
void fun9(int arr[], int start_index, int end_index)
{
if (start_index >= end_index)
return;
int min_index;
int temp;
/* 함수 minIndex()는 배열 arr[start_index...end_index]에서 최소값의 인덱스를 반환한다고 가정*/
min_index = minIndex(arr, start_index, end_index);
temp = arr[start_index];
arr[start_index] = arr[min_index];
arr[min_index] = temp;
fun9(arr, start_index + 1, end_index);
}
fun9 함수는 배열을 오름차순으로 정렬하는 함수로 보인다. 이는 선택 정렬(Selection Sort) 알고리즘을 기반으로 하는 재귀적 구현이다. 선택 정렬은 배열에서 가장 작은 값을 찾아서 첫 번째 위치에 배치하고, 그 다음으로 작은 값을 두 번째 위치에 배치하는 방식으로 진행된다.
동작 원리
fun9 함수는 재귀적으로 배열을 처리하면서, 주어진 구간에서 최소값을 찾아 해당 값을 배열의 첫 번째 위치로 교환하고, 그런 다음 그 이후의 구간에 대해 같은 작업을 반복한다.
세부 동작:
- 재귀 종료 조건:
- start_index >= end_index이면, 즉 시작 인덱스가 끝 인덱스보다 크거나 같으면 더 이상 정렬할 필요가 없으므로 종료된다.
- 최소값의 인덱스를 찾기:
- minIndex(arr, start_index, end_index) 함수는 배열의 start_index부터 end_index까지의 범위에서 최소값을 찾고, 그 최소값의 인덱스를 반환한다고 가정한다.
- 교환 작업:
- 배열의 start_index 위치와 최소값의 인덱스 위치를 교환한다. 이를 통해 최소값을 start_index 위치로 이동시킨다.
- 재귀 호출:
- start_index + 1부터 end_index까지 동일한 작업을 반복하기 위해 fun9을 재귀적으로 호출한다.
선택 정렬의 동작:
선택 정렬은 n번의 패스(pass)를 통해 정렬을 진행한다. 매번 가장 작은 값을 찾아서 그 값을 현재 위치와 교환하는 방식으로 진행된다.
예시 실행:
배열 arr = {64, 25, 12, 22, 11}에 대해 fun9가 어떻게 동작하는지 예시를 들어 보자.
- 첫 번째 호출: fun9(arr, 0, 5)
- arr[0...4]에서 최소값을 찾음. 최소값은 11이고, 이를 arr[0]과 교환함.
- 교환 후: arr = {11, 25, 12, 22, 64}.
- 그 다음, fun9(arr, 1, 5)를 호출.
- 두 번째 호출: fun9(arr, 1, 5)
- arr[1...4]에서 최소값을 찾음. 최소값은 12이고, 이를 arr[1]과 교환함.
- 교환 후: arr = {11, 12, 25, 22, 64}.
- 그 다음, fun9(arr, 2, 5)를 호출.
- 세 번째 호출: fun9(arr, 2, 5)
- arr[2...4]에서 최소값을 찾음. 최소값은 22이고, 이를 arr[2]와 교환함.
- 교환 후: arr = {11, 12, 22, 25, 64}.
- 그 다음, fun9(arr, 3, 5)를 호출.
- 네 번째 호출: fun9(arr, 3, 5)
- arr[3...4]에서 최소값을 찾음. 최소값은 25이고, 이를 arr[3]와 교환함.
- 교환 후: arr = {11, 12, 22, 25, 64}.
- 그 다음, fun9(arr, 4, 5)를 호출.
- 다섯 번째 호출: fun9(arr, 4, 5)
- arr[4...4]에서 최소값을 찾음. 배열의 길이가 1이므로 더 이상 교환할 필요가 없음.
- 종료.
결과:
최종적으로 배열은 오름차순으로 정렬된다:
arr = {11, 12, 22, 25, 64}.
핵심 요약
- fun9는 **선택 정렬(Selection Sort)**을 재귀적으로 구현한 함수이다.
- 최소값을 찾아서 교환하는 방식으로 정렬한다.
- 함수가 배열을 정렬하기 위해 재귀적으로 배열을 반복해서 처리한다.
10번
void fun10(int arr[], int n, int t)
{
if (n == 0)
arr[0] = t;
else if (t >= arr[n - 1])
arr[n] = t;
else
{
arr[n] = arr[n - 1];
fun10(arr, n - 1, t);
}
}
int main()
{
int data[] = { 7,1,3,8,1,9,2,10 };
int result[8];
for (int i = 0; i < 8; i++)
fun10(result, i, data[i]);
}함수 fun10 설명
함수 fun10은 주어진 배열 arr의 처음 n개의 요소들을 정렬된 상태로 유지하면서 새로운 값 t를 적절한 위치에 삽입하는 역할을 합니다.
동작 방식:
- 기저 조건 (n == 0): 만약 n이 0이면 (배열이 비어있으면), t를 배열의 첫 번째 요소(arr[0])로 설정합니다.
- t가 배열의 마지막 요소보다 크거나 같을 경우 (t >= arr[n - 1]): t가 현재 배열의 마지막 요소보다 크거나 같으면, t를 배열의 다음 빈 위치(arr[n])에 추가합니다. 이는 t가 정렬된 순서에서 가장 큰 값이므로 맨 뒤에 위치해야 함을 의미합니다.
- t가 배열의 마지막 요소보다 작을 경우 (else):
- 현재 배열의 마지막 요소(arr[n-1])를 다음 빈 위치(arr[n])로 옮깁니다.
- fun10 함수를 재귀적으로 호출합니다. 이때 n은 1 감소하고, t는 그대로 전달됩니다. 이는 t보다 큰 요소를 오른쪽으로 한 칸씩 밀어내면서 t가 삽입될 올바른 위치를 찾기 위한 과정입니다.
main 함수에서의 호출 방식:
main 함수에서는 data 배열의 각 요소를 순차적으로 fun10 함수에 전달하여 result 배열에 삽입합니다. 루프가 진행됨에 따라 result 배열은 data 배열의 요소들이 정렬된 상태로 채워지게 됩니다.
예시:
main 함수에서 처음 호출되는 fun10(result, 0, data[0])은 fun10(result, 0, 7)이 됩니다. n이 0이므로 result[0]은 7이 됩니다.
두 번째 호출 fun10(result, 1, data[1])은 fun10(result, 1, 1)이 됩니다. t (1)은 arr[n-1] (현재 result[0]인 7)보다 작으므로, result[1]에 result[0]의 값 7이 복사되고, fun10(result, 0, 1)이 재귀적으로 호출됩니다. 이 재귀 호출에서 result[0]은 1로 설정됩니다. 따라서 result 배열은 {1, 7}이 됩니다.
이러한 과정을 반복하면 result 배열에는 data 배열의 요소들이 정렬된 순서로 삽입되게 됩니다.
결론적으로, fun10 함수는 main 함수에서 호출될 때마다 data 배열의 원소를 하나씩 가져와 result 배열에 정렬된 방식으로 삽입하는 역할을 수행합니다. main 함수가 종료되면 result 배열은 data 배열의 모든 요소를 오름차순으로 정렬한 결과를 갖게 됩니다.
11번
기존코드
이 함수의 구조는 이렇게 돼:
- level번째 퀸까지 놓아봤을 때 유효하지 않으면(false) 그냥 중단.
- level == N이면, 퀸을 N개 다 놓은 거니까 → 해를 하나 찾았음 → true 반환.
- 그렇지 않으면, 가능한 열을 1부터 N까지 돌면서 퀸을 놓고 → 다음 level로 넘어감.
- 만약 한 번이라도 다음 단계에서 해가 발견되면 true를 반환해서 바로 종료
#include <iostream>
using namespace std;
const int N = 8; // 원하는 N값으로 수정 가능
int cols[N + 1];
int solutionCount = 0;
// 가정: promising 함수는 이미 정의되어 있다고 가정
bool promising(int level) {
for (int i = 1; i < level; i++) {
if (cols[i] == cols[level] || abs(cols[i] - cols[level]) == level - i)
return false;
}
return true;
}
void queens(int level) {
if (!promising(level))
return;
else if (level == N)
solutionCount++; // 해를 하나 찾았을 때 count 증가
else {
for (int i = 1; i <= N; i++) {
cols[level + 1] = i;
queens(level + 1);
}
}
}
int main() {
queens(0);
cout << "서로 다른 해의 개수: " << solutionCount << endl;
return 0;
}
🔄 핵심 변형 요소 1: bool → void 로 바꾼 이유
원래는 bool 타입:
- 해를 찾으면 true 반환, 못 찾으면 false 반환.
- 주 목적: 해가 존재하는지만 확인하려는 구조.
- 해를 찾는 즉시 return true;로 종료함.
지금은 void 타입:
- 해를 찾더라도 종료하지 않고, 계속 재귀를 진행함.
- 모든 경우를 탐색해야 하므로 true/false로 멈출 필요가 없음.
- 대신, 해를 찾았을 때는 단순히 solutionCount++ 해서 개수만 올림.
- 즉, 종료 조건으로 return 값을 쓰지 않음 → 모든 해를 보기 위해!
✔️ 요약:
→ bool은 "찾았는가?"만 중요할 때
→ void는 "끝까지 다 확인하자"가 목표일 때 사용해!
if (queens(level + 1))
return true;
- 다음 단계에서 해가 하나라도 나오면 바로 멈춤.
- 그 뒤에 나올 수 있는 해는 무시됨.
queens(level + 1);- 다음 단계로 무조건 계속 탐색.
- return하지 않음 → 끝까지 감.
- 모든 경우를 놓치지 않고 탐색 가능.
- 해를 찾을 때마다 개수만 세고 계속 진행함.
✔️ 요약:
→ if (queens(...)) return true;는 해 하나만 필요할 때
→ queens(...);는 모든 해가 필요할 때!
int solutionCount = 0;
- 전역 변수로 선언해서 해를 찾을 때마다 하나씩 더함.
- level == N이면 해를 완성한 것이므로 solutionCount++.
✔️ 원래 코드에서는 "해를 찾았다"의 의미는 return true였지만,
✔️ 지금은 해를 찾으면 그걸 개수로 저장하는 방식으로 변경된 거야.
int countQueens(int level) {
if (!promising(level)) {
return 0; // 유망하지 않으면 해가 없음
} else if (level == N) {
return 1; // N개의 퀸을 모두 배치했으므로 해를 찾음
}
int count = 0;
for (int i = 1; i <= N; i++) {
cols[level + 1] = i;
count += countQueens(level + 1); // 다음 행의 해 개수를 누적
}
return count;
}
int main() {
int numberOfSolutions = countQueens(0); // 0번 행부터 시작
// numberOfSolutions를 출력
return 0;
}
12번
int countMazePaths(int x, int y) {
// 경계 검사 및 장애물 확인
if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] != PATHWAY_COLOUR)
return 0;
// 목표 지점에 도달한 경우
if (x == N - 1 && y == N - 1) {
maze[x][y] = PATH_COLOUR;
return 1;
}
// 현재 위치 방문 표시
maze[x][y] = PATH_COLOUR;
// 네 방향으로 재귀적으로 경로를 탐색하고 그 합을 리턴
int pathCount = 0;
pathCount += countMazePaths(x - 1, y); // 위
pathCount += countMazePaths(x, y + 1); // 오른쪽
pathCount += countMazePaths(x + 1, y); // 아래
pathCount += countMazePaths(x, y - 1); // 왼쪽
// 백트래킹: 현재 위치를 다시 막힌 곳으로 설정
maze[x][y] = BLOCKED_COLOUR;
return pathCount;
}
int countMazePaths(int x, int y) {
// 범위 벗어나거나 길이 아닌 경우
if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] != PATHWAY_COLOUR)
return 0;
// 출구에 도달한 경우: 경로 1개 발견!
if (x == N-1 && y == N-1)
return 1;
// 현재 위치를 방문했다고 표시
maze[x][y] = PATH_COLOUR;
// 4방향으로 이동해서 각각 경로 개수를 더함
int count = 0;
count += countMazePaths(x-1, y); // 위
count += countMazePaths(x, y+1); // 오른쪽
count += countMazePaths(x+1, y); // 아래
count += countMazePaths(x, y-1); // 왼쪽
// 백트래킹: 다른 경로도 탐색할 수 있도록 방문 표시 해제
maze[x][y] = PATHWAY_COLOUR;
return count;
}기존은 상하좌우 하나라도 출구에 도착하면 true를 리턴하며 하나의 경로만 찾고 끝이며 나머지 경로를 확인하지 않습니다.
bool -> int 경로의 수를 세야 하므로 int로 바꾼 후
||가 아닌 모든 경로를 더하는 함수로 count += 해당 위치들을 다 더해줍니다.
13번
function canPartition(nums):
total_sum = sum(nums)
if total_sum % 2 != 0:
return false // 합이 홀수라면 불가능
target = total_sum / 2
return backtrack(nums, 0, 0, target)
function backtrack(nums, index, current_sum, target):
if current_sum == target:
return true // 한 집합의 합이 target과 같으면 나머지 집합의 합도 동일하므로 참
if current_sum > target or index >= len(nums):
return false // 현재 합이 target을 초과하면 더 이상 탐색하지 않음
// 현재 index의 정수를 집합 1에 넣는 경우
if backtrack(nums, index + 1, current_sum + nums[index], target):
return true
// 현재 index의 정수를 집합 2에 넣는 경우
if backtrack(nums, index + 1, current_sum, target):
return true
return false
- canPartition(nums)는 주어진 정수 리스트 nums로부터 총합을 구하고, 그 합이 홀수라면 바로 false를 반환합니다. 그렇지 않으면, 목표 값 target = total_sum / 2를 설정하고 backtrack() 함수를 호출하여 가능한 분할을 탐색합니다.
- backtrack(nums, index, current_sum, target)는 현재까지 집합 1에 포함된 값의 합이 current_sum일 때, 주어진 index부터 시작하여 각 정수를 집합 1 또는 집합 2에 추가하는 방식으로 탐색합니다. 만약 current_sum이 target과 같으면 집합 1과 집합 2의 합이 동일함을 알 수 있으므로 true를 반환합니다. current_sum이 target을 초과하면 더 이상 탐색할 필요가 없으므로 false를 반환합니다.
상태 공간 트리 (State-Space Tree)
(0, 0) ← index 0, currentSum 0
/ \
포함 O 포함 X
/ \
(1,1) (1,0)
/ \ / \
(2,6) (2,1) (2,5) (2,0)
... ...
- 각 노드는 (index, 현재까지의 합)을 의미
- 리프 노드에 도달했을 때, 현재 합 == target이면 성공
function canPartition(S):
total = sum of all elements in S
if total % 2 != 0:
return false
target = total / 2
return subsetSum(S, 0, 0, target)
function subsetSum(S, index, currentSum, target):
if currentSum == target:
return true
if currentSum > target or index == len(S):
return false
// 두 가지 선택: 포함하거나 포함하지 않거나
if subsetSum(S, index + 1, currentSum + S[index], target):
return true
if subsetSum(S, index + 1, currentSum, target):
return true
return false
🧩 가지치기(Pruning) 전략
currentSum > target → 더 이상 탐색하지 않음 (불가능)
정렬하고 큰 수부터 넣는 것도 효율성 ↑
상태 공간 트리는 각 단계에서 선택을 할 수 있는 두 가지 가지를 분기점으로 하고, 그 선택을 진행하며 탐색을 합니다. 각 정수에 대해 그 정수를 집합 1에 포함할지 아니면 집합 2에 포함할지를 결정하는 방식으로 트리가 확장됩니다.
- 루트 노드는 정수들을 아직 선택하지 않은 상태입니다.
- 자식 노드는 각 정수를 집합 1이나 집합 2로 배치한 상태를 나타냅니다.
- 각 노드는 두 집합의 합이 동일한지 여부를 확인하며, 모든 가능한 분할을 탐색합니다.
알고리즘 설명
- 합을 구한다: 먼저 주어진 N개의 정수들의 합을 구하고, 그 합이 홀수라면 바로 false를 반환합니다. 왜냐하면, 홀수는 두 집합으로 나누어 떨어지지 않기 때문입니다.
- 백트래킹을 이용한 탐색:
- 정수들을 집합 1 또는 집합 2로 나누는 방법을 백트래킹 방식으로 탐색합니다.
- 각 집합의 합을 추적하며, 두 집합의 합이 동일한지 확인합니다.
상태 공간 트리 예시
- 주어진 정수: {1, 5, 11, 5} (합: 22)
- 트리의 분기점:
- 첫 번째 정수 1을 집합 1에 넣거나 집합 2에 넣을 수 있습니다.
- 두 번째 정수 5를 집합 1에 넣거나 집합 2에 넣을 수 있습니다.
- 나머지 정수도 마찬가지로 분기하여 탐색합니다.
트리의 깊이가 N이 되고, 각 분기에서 선택을 하는 방식으로
13번
문제 설명:
- 입력: 그래프의 노드 수 n, 간선 정보, 사용할 수 있는 색의 수 m.
- 목표: 각 노드를 최대 m개의 색 중 하나로 칠하면서 인접한 노드들이 동일한 색을 가지지 않도록 할 수 있는지 검사.
상태 공간 트리 (State-Space Tree)
상태 공간 트리는 각 노드를 색칠하는 과정에서 분기됩니다. 트리의 각 노드는 현재까지 색칠된 노드들을 나타내며, 각 분기에서는 현재 노드에 사용할 색을 선택합니다. 트리의 깊이는 그래프의 노드 수와 같고, 각 깊이에서 사용할 색을 선택합니다.
- 루트 노드는 아무것도 색칠하지 않은 상태입니다.
- 자식 노드는 각 노드를 색칠한 상태로, 노드를 색칠할 때마다 가능한 색 중 하나를 선택하고, 그 색이 인접한 노드들과 충돌하지 않도록 합니다.
- 만약 인접한 두 노드가 동일한 색을 가지게 되면, 그 경로를 더 이상 탐색하지 않고 되돌아갑니다.
백트래킹 알고리즘
이 문제의 해결은 각 노드를 하나씩 색칠하며, 색이 인접한 노드들과 충돌하지 않으면 계속 진행하고, 그렇지 않으면 백트래킹을 통해 이전에 색칠한 노드를 다시 선택하도록 합니다.
알고리즘 설명
- 그래프 표현: 그래프는 인접 리스트나 인접 행렬로 표현됩니다.
- 색칠 함수: 각 노드를 색칠하면서 인접 노드들과 색이 충돌하는지 확인합니다.
- 백트래킹: 가능한 색을 하나씩 선택하고, 그 색이 유효한지 확인한 후, 유효하면 다음 노드로 넘어가고, 그렇지 않으면 다시 색을 변경하여 탐색을 계속합니다.
- 기저 조건: 모든 노드를 색칠할 수 있다면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
상태 공간 트리 예시
- 각 노드마다 m개의 색 중 하나를 선택할 수 있습니다.
- 예를 들어, m = 3일 때 색은 1, 2, 3이라 가정하면, 트리의 각 분기에서 현재 노드에 대해 가능한 색을 선택하고, 이 색이 이미 색칠된 인접 노드와 충돌하는지 확인합니다.
function isSafe(node, color, graph, colors):
for each neighbor in graph[node]:
if colors[neighbor] == color: // 인접한 노드가 이미 같은 색을 가지면 안전하지 않음
return false
return true
function graphColoring(graph, m, n, colors, node):
if node == n: // 모든 노드가 색칠되었으면 성공
return true
for color = 1 to m: // 가능한 색을 하나씩 시도
if isSafe(node, color, graph, colors): // 이 색이 안전한지 확인
colors[node] = color // 색칠하기
if graphColoring(graph, m, n, colors, node + 1): // 다음 노드로 이동
return true
colors[node] = 0 // 색을 되돌리고 백트래킹
return false // 모든 색을 시도했으나 불가능하면 false 반환
function solveGraphColoring(graph, m, n):
colors = array of size n, initialized to 0 // 모든 노드는 색칠되지 않음
if graphColoring(graph, m, n, colors, 0): // 0번 노드부터 색칠 시작
return colors // 성공적으로 색칠된 결과 반환
else:
return "No solution" // 불가능한 경우
- sSafe(node, color, graph, colors):
- node에 color를 칠할 수 있는지 확인하는 함수입니다.
- 인접한 모든 노드를 확인하여, 인접한 노드 중에서 이미 같은 색을 칠한 노드가 있으면 false를 반환하고, 없으면 true를 반환합니다.
- graphColoring(graph, m, n, colors, node):
- node부터 시작해서 모든 노드를 색칠하는 재귀 함수입니다.
- m개의 색 중 하나를 선택하고, isSafe를 통해 색을 칠할 수 있는지 확인한 후, 칠할 수 있으면 그 색으로 칠하고 다음 노드를 처리합니다.
- 만약 모든 노드를 색칠할 수 있으면 true를 반환하고, 그렇지 않으면 백트래킹하여 색을 되돌립니다.
- solveGraphColoring(graph, m, n):
- graph는 그래프의 인접 리스트 표현이고, m은 색의 개수, n은 노드의 개수입니다.
- graphColoring 함수를 호출하여, 색칠이 가능한지 여부를 확인하고 결과를 반환합니다.
14번
🎯 문제 요약
- 그래프 G = (V, E)가 주어지고, 사용할 수 있는 색의 개수 m도 주어짐
- 그래프의 노드를 각각 색칠하면서, 모든 인접 노드 쌍이 다른 색이 되게 해야 함
- 목표: 그래프가 m가지 색으로 색칠 가능한지 여부를 확인
🧠 상태공간트리 설계
- 각 노드는 "노드 i에 어떤 색을 칠했는가"에 해당하는 상태
- 레벨 i는 i번째 노드를 색칠하는 단계
- 각 레벨마다 가능한 색(1~m) 중에서 하나 선택
- 이전까지의 색칠 상태를 참고해서, 인접 노드와 색이 겹치면 백트래킹
(빈 상태)
/ | \
노드 0에 1 2 3 색
/ | \ ...
노드 1에 가능한 색
...
(색이 충돌하면 해당 가지 자름)⚙️ 알고리즘 핵심 아이디어
- color[i] = k는 i번 노드에 k번 색을 칠한다는 의미
- 재귀적으로 노드들을 색칠해나감
- 현재 노드에 색을 칠할 때, 인접 노드들과 같은 색이 되면 안 됨
- 조건이 만족되지 않으면 다음 색 시도 또는 백트래킹
function graphColoring(graph, m):
n = number of vertices in graph
color = array of size n, initialized to 0
if solve(graph, m, color, 0):
return true
else:
return false
function solve(graph, m, color, node):
if node == n:
return true // 모든 노드 색칠 성공!
for c in 1 to m:
if isSafe(graph, color, node, c):
color[node] = c
if solve(graph, m, color, node + 1):
return true
color[node] = 0 // 백트래킹
return false
function isSafe(graph, color, node, c):
for each neighbor in graph[node]:
if color[neighbor] == c:
return false
return true✅ 각 함수 설명
- graph: 인접 리스트 또는 인접 행렬로 표현된 그래프
- m: 사용할 수 있는 색의 개수
- color: 각 노드의 색깔을 저장하는 배열
- node: 현재 색칠 중인 노드 번호
- isSafe: 현재 색을 이 노드에 칠해도 인접 노드들과 충돌이 없는지 확인
(0, 0, 0) ← 시작 상태 (아직 아무도 색 안 칠함)
/ | \
0→1 0→2 0→3 ← 노드 0에 색 1, 2, 3 중 선택
/ | \
(1,0,0) (2,0,0) (3,0,0)
/|\ /|\ /|\
색1X ↓ 색2 색3 ... 각각 노드 1의 색을 시도
(1,2,0) (1,3,0) ... 등등
↓
노드 2 색 선택 (1,2,3 중 안전한 것만)상태공간트리 말로 설명 (노드 순서대로)
▶️ 1단계: 노드 0 색칠
- 트리의 루트 노드는 "아무 노드도 색칠하지 않은 상태"
- 이 루트에서 노드 0을 색칠하는 세 가지 경우가 나와:
- 노드 0에 색 1을 칠한다
- 노드 0에 색 2를 칠한다
- 노드 0에 색 3을 칠한다
→ 이게 상태공간트리의 첫 번째 분기야 (총 3개의 가지)
▶️ 2단계: 노드 1 색칠
- 이제 각 경우마다 노드 1을 색칠하려고 해
- 노드 0과 인접하니까, 노드 0과는 다른 색만 선택 가능해
- 예를 들어, 노드 0이 색 1이라면:
- 노드 1에는 색 1 ❌ (같아서 불가) → 이 가지는 가지치기
- 노드 1에는 색 2 ✅
- 노드 1에는 색 3 ✅
→ 그래서 노드 1에서는 최대 2개의 유망한 자식 노드가 생겨
▶️ 3단계: 노드 2 색칠
- 이제 노드 2를 색칠해
- 노드 2는 노드 0, 노드 1 둘 다와 인접해
- 따라서, 노드 0과 노드 1 모두와 다른 색이어야 해
- 예를 들어, 노드 0이 색 1, 노드 1이 색 2인 경우:
- 노드 2는 색 1 ❌ (노드 0과 충돌)
- 노드 2는 색 2 ❌ (노드 1과 충돌)
- 노드 2는 색 3 ✅
→ 이 경우에만 모든 노드가 조건을 만족하므로 성공!
✅ 최종적으로
트리에서 어떤 경로가 모든 노드를 조건에 맞게 색칠했다면,
그건 하나의 해결 경로야. 이 경로가 하나라도 있다면 문제는 "가능"한 거고,
전부 가지치기로 잘려버리면 "불가능"하다는 거야.
📌 정리하면
- 상태공간트리의 각 레벨은 그래프의 노드 하나를 색칠하는 단계야.
- 각 레벨에서 가능한 **색 선택지(m개)**만큼 가지가 생겨.
- 하지만 색을 선택할 때, 인접 노드와 겹치면 가지를 자른다 (백트래킹).
- 트리의 리프 노드까지 성공적으로 도달하면, 모든 노드 색칠에 성공한 거야.
'IT 프로그래밍 > 알고리즘' 카테고리의 다른 글
| [알고리즘] mergesort (0) | 2025.03.27 |
|---|---|
| [알고리즘] 정렬 (0) | 2025.03.27 |
| [알고리즘] 멱집합 (0) | 2025.03.20 |
| [알고리즘] 그룹액티비티1 설명 해석 (0) | 2025.03.16 |
| [알고리즘] 이진 검색과 정렬 (0) | 2025.03.15 |