문제
- 백준, 골드 1, https://www.acmicpc.net/problem/1311
- 풀이 날짜: 2025.1.29.
- 풀이 시간: 15:17~16:30, 안 돼서 GPT 킴, 17:28에 DFS 방식으로 해결(총 2시간 11분)
- 알고리즘 분류: 비트필드를 이용한 다이나믹 프로그래밍
- 사용 언어: C++
문제 해설
해당 문제는 비트필드를 이용한 다이나믹 프로그래밍을 활용하는 문제이다.
문제의 정답을 탐색할 때 탐욕법이나 다른 방법을 사용할 수 없으므로, 완전 탐색으로 모든 경우의 수를 측정해야 한다. 그런데 4명의 사람이 순차적으로 1-2-3-4번 일을 맡는 경우와 2-1-3-4번 일을 맡는 경우, 뒤의 3-4번 일의 비용을 계산할 땐 중복 계산이 발생하게 된다.
이러한 중복 계산을 피하려면 상태를 저장하는 비트필드 기반 다이나믹 프로그래밍이 필요하게 된다.
다만 사람과 일의 수가 20개로 사람과 일의 상태 모두를 비트필드 형태로 인덱싱하는 것은 불가능하다. 왜냐하면 1 << 20 Byte = 1,048,576 = 1GB이고 사람, 일 모두에 대해 비트필드를 입력하면 (1 << 20) * (1 << 20) = 1TB의 크기를 요구하게 된다(정확히는 int 타입으로 지정하면 하나의 자료에 4 Byte가 필요하므로 4TB 필요).
따라서 둘 모두를 저장할 수는 없으며, 무슨 작업이 완료되었는지 비트필드를 통해 작업 상태를 저장하는 것이 적절하다(혹은, 누가 작업을 완료했는지 저장하는 방법도 가능하겠다).
실패한 풀이: BFS를 통한 풀이법의 문제
나는 여기에서 BFS를 통해 풀이하려고 했다.
각 사람이 0번 일을 수행하는 경우부터 시작하여, 사람을 하나씩 추가하면서 최소 수행 비용을 계산하도록 했다.
처음엔 아무런 일도 수행하지 않다가, 0번 일, 1번 일, 2번 일, …, (N-1) 번 일까지 추가하도록 한다.
이때, 계산량을 줄이기 위해 현재 일이 k번째 일이라면 (k-1) 번째 일에서 갱신했던 비트필드에 대해서만 갱신하도록 했다.
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int cost[20][20];
int dp[(1 << 20) - 1];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> cost[i][j];
}
}
memset(dp, -1, sizeof(dp));
dp[0] = 0;
queue<int> indexQueue;
indexQueue.push(0);
for (int job = 0; job < N; job++)
{
int indices = indexQueue.size();
for (int repeat = 0; repeat < indices; repeat++)
{
int idx = indexQueue.front();
indexQueue.pop();
for (int i = 0; i < N; i++)
{
if ((idx & (1 << i)) != 0)
continue;
if (dp[idx | (1 << i)] == -1)
{
dp[idx | (1 << i)] = dp[idx] + cost[i][job];
indexQueue.push(idx | (1 << i));
}
else if (dp[idx] + cost[i][job] < dp[idx | (1 << i)])
{
dp[idx | (1 << i)] = dp[idx] + cost[i][job];
}
}
}
}
cout << dp[(1 << N) - 1] << '\n';
return 0;
}그런데 계산에서 모든 경우의 수를 세지 못하는 문제가 발생했다.
이에 대한 ChatGPT의 답변은 이러하다.
ChatGPT의 답변(GPT 4o mini 기준)
- BFS 기반 접근 방식이 최적 경로를 항상 보장하지 않을 수 있음
- 일반적으로 비트마스크 DP 문제는 DFS + 메모이제이션 (Top-down) 또는 반복문 (Bottom-up)을 사용하는 것이 일반적입니다.
- BFS를 사용하면 방문 순서에 따라 dp 갱신이 잘못될 가능성이 큽니다.
- 특히, 큐에 있는 상태가 항상 최적의 상태를 유지하지 못할 수 있습니다.
dp[idx | (1 << i)]상태 갱신 방식이 잘못될 가능성이 있음
dp[idx] + cost[i][job]을 계산할 때 이전 상태(idx)가 최적 상태가 아닐 수도 있음- 즉, 이미 dp 값이 설정된 상태(
dp[idx | (1 << i)] != -1)에서도 현재 경로(dp[idx] + cost[i][job])가 더 나을 수 있음- 그러나
if-else조건문에서 특정 조건에서만 업데이트되므로 일부 최적 경로가 반영되지 않을 가능성이 있음
사실 위에서 답변해 준 경우에 해당하는 반례는 찾지 못했다.
다만, 위 답변을 잘 생각해 보면 최단 경로 알고리즘을 떠올릴 수 있다.
최단 경로를 구할 때 방문하는 정점의 순서를 제대로 정하지 않으면, 이미 방문한 정점 V에 대해서 최단 경로를 발견하는 일이 발생할 수 있다. 이때 V와 인접한 모든 노드에 대해 최단 경로를 다시 탐색해야 제대로 된 정답을 얻을 수 있다.
이러한 문제를 피하려면, 비트마스크 DP 문제는 큐를 사용하여 BFS로 해결하기보단 GPT에서 답변해 준 것처럼 일반적으로 DFS + 메모이제이션 (Top-down) 또는 반복문 (Bottom-up)을 이용하여 해결하는 것이 적합한 것으로 보인다.
Bottom-up 방식
먼저 Bottom-up 방식부터 보자.
현재 해결하는 방식과 유사해 보이지만, 방문하는 인덱스의 순서가 다르고 몇 번째 사람을 조사할지 확인하는 방법이 다르다. 여기에서는 0부터 차례대로 비트필드 인덱스를 증가시키는데 이렇게 되면 당연히 최적의 순서로 조사를 수행할 수 있다.
만약 비트필드가 수행한 일의 상태를 가리킬 때
dp[mask] = (mask)에 해당하는 일을 수행했을 때 비용의 최솟값이라 하자.
이때 비트필드는 아래와 같은 순서로 방문하게 될 건데(오른쪽부터 0번, 1번, …, (N-1) 번 일에 대한 수행 상태),
0001 → 0010 → 0011 → 0100 → 0101 → 0110 → 0111 → …
잘 보면 0번 일과 1번 일을 개별적으로 마치고 나서야 0번, 1번 두 개를 마쳤을 때 비용을 계산하게 된다. 즉, 개별적인 일을 모두 마치고 이들 모두를 수행하는 경우의 비용을 계산하게 된다.
이렇게 하면 조사를 수행할 때 최적의 순서로 조사할 수 있다.
#include <iostream>
#include <climits>
using namespace std;
#define INF 987654321
int cost[20][20];
int dp[(1 << 20) - 1];
// bits에서 1의 개수를 센다.
int count_bits(int bits)
{
int count = 0;
while (bits)
{
count += bits & 0x01;
bits = bits >> 1;
}
return count;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> cost[i][j];
}
}
// 0번 이외의 인덱스는 최대값으로 설정한다.
dp[0] = 0;
for (int i = 1; i < (1 << N); i++)
dp[i] = INF;
// 모든 비트필드를 순차적으로 검사한다(Bottom-up).
for (int i = 0; i < (1 << N); i++)
{
// x: 다음으로 수행할 사람의 번호
// 해결한 일의 개수가 x개라면 0, 1, ..., (x-1)번째 사람까지 일을 수행했다고 보도록 한다.
// 이때 x는 1인 비트의 개수를 세서 구할 수 있다.
int x = count_bits(i);
// 할당할 일 j를 찾는다.
for (int j = 0; j < N; j++)
{
// 이미 j번째 일을 수행했다면, 검사하지 않음
if ((i & (1 << j)) != 0)
continue;
int next = (i | (1 << j));
// 최소값을 갱신한다.
if (dp[i] + cost[x][j] < dp[next])
{
dp[next] = dp[i] + cost[x][j];
}
}
}
cout << dp[(1 << N) - 1] << '\n';
return 0;
}DFS를 사용하는 방법
dfs를 사용하는 코드는 굉장히 짧다.
이때 dp는 위와 마찬가지로 정의한다.
dp[mask] = (mask)에 해당하는 일을 수행했을 때 비용의 최솟값
한편, 조사할 때 호출하는 dfs는 다음을 의미한다.
dfs(person, mask) = person번째 사람이 일을 수행할 때 비용의 최소 값.
(현재 완료된 작업은 mask에 해당한다.)
이때 한 사람씩 추가해 가며 탐색하는데, min으로 최솟값을 구한다.
이때 dp가 -1이라면 아직 조사하지 않았으므로 계산을 수행하지만 -1이 아니라면 이미 조사했으므로 dp 값을 반환한다.
person이 N이라면 N명을 모두 작업을 배정한 것이므로 비용으로 0을 반환한다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
int cost[20][20];
int dp[(1 << 20) - 1];
int N;
int dfs(int person, int mask)
{
if (person == N)
return 0;
if (dp[mask] != -1)
return dp[mask];
// person에게 job번 일을 맡긴다
int result = INT_MAX;
for (int job = 0; job < N; job++)
{
if (!(mask & (1 << job)))
{
result = min(result, dfs(person + 1, mask | (1 << job)) + cost[person][job]);
}
}
dp[mask] = result;
return result;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> cost[i][j];
memset(dp, -1, sizeof(dp));
cout << dfs(0, 0) << '\n';
return 0;
}'Problem Solving > Backjoon' 카테고리의 다른 글
| 백준 2075번 - N번째 큰 수: 약간 더 빠른 코드 (0) | 2025.02.04 |
|---|---|
| 백준 1562번 - 계단 수 풀이(C++) (0) | 2025.01.28 |
| 백준 9252번 - LCS 2 (1) | 2025.01.24 |
| 백준 1018 체스판 다시 칠하기 (1) | 2024.12.27 |
| 백준 2922 즐거운 단어 (0) | 2021.02.16 |
댓글