백준 1029번 그림교환 문제 해설, 동적계획법 변형문제 해법!
by injae Kim
백준 1029번 그림교환 문제 해설
solved.ac 기준 골드 1 난이도의 문제입니다. 다이나믹 프로그래밍, 그래프, DFS, 비트마스킹 을 사용하여 문제를 해결하였습니다.
문제 자체는 다이나믹 프로그래밍으로 분류 되지만 중간 중간 그래프, DFS, 비트마스킹 등의 개념이 들어가 쉽게 풀리지 않았습니다.
이 문제는 백준 2098번 외판원 순회 를 푸셨다는 전제하에 설명하겠습니다.
기본적인 다이나믹 프로그래밍에 대한 개념과 비트마스킹을 적용하는 방법을 알고 있어야만 접근할 수 있는 문제였습니다.
만약 외판원 순회 문제를 아직 풀지 않으셨다면! 한번 풀어보신 후에 이 글을 읽으시길 추천드립니다.
문제
예술을 사랑하는 사람들이 시장에 모여서 그들의 그림을 서로 거래하려고 한다. 모든 그림의 거래는 다음과
같은 조건을 만족해야 한다.
그림을 팔 때, 그림을 산 가격보다 크거나 같은 가격으로 팔아야 한다.
같은 그림을 두 번 이상 사는 것은 불가능하다.
방금 시장에 새로운 그림이 들어왔다. 1번 아티스트는 그 그림을 외부 상인에게 가격 0을 주고 샀다.
이제 그 그림을 자신의 예술가 친구들에게 팔려고 한다. 위의 조건을 모두 만족하는 거래만 이루어진다고
가정했을 때, 그림을 소유했던 사람의 수의 최댓값을 출력하는 프로그램을 작성하시오.
(1번 아티스트와 마지막으로 그 그림을 소유한 사람도 포함한다).
입력
첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가
i번 예술가에게 그 그림을 살 때의 가격이다. 모든 가격은 0이 제일 낮은 가격이고, 9가 제일 높은 가격이다.
출력
첫째 줄에 그 그림을 소유 했던 사람들 (잠시라도 소유했던 사람도 포함)의 최댓값을 출력한다.
예제입력
3
022
101
110
예제출력
2
문제 풀이
백준 2098번 외판원 순회 를 풀어 보셨다면, 이 문제도 기본적으로 다이나믹 프로그래밍 + 비트마스킹 의 조합으로 접근하셨을 거라고 생각합니다. 저도 그랬거든요.
우리가 원하는 답은, 현재 예술가가 그림을 팔때, 가장 많이 그림을 팔 수 있는 경로의 사람 수 입니다.
우선 다이나믹 프로그래밍의 접근 방법 대로 문제를 정의하고 풀어보겠습니다.
문제정의와 부분문제로 쪼개기, 점화식 만들고 메모이제이션을 적용하는 방법에 대한 그림입니다.
따라서 우리가 원하는 답을
longestPath () = 현재 예술가가 그림을 팔때, 가장 많이 그림을 팔 수 있는 경로의 사람 수
로 정의 해 볼 수 있겠죠.
이때 longestPath(), 즉 현재 그림이 팔린 상태 를 나타내려면 현재 그림을 가지고있는 예술가 번호 cur 와, 그림이 누구에게 팔렸었는지를 나타내는 비트마스킹으로 나타낸 visited, 현재 그림을 가지고있는 예술가가 그 전에 얼마에 그림을 샀는지를 의미하는 prePrice 가 필요합니다.
보통 다이나믹 프로그래밍 문제에서는 cur 와 visited 까지만 필요했는데, 이 문제에선 prePrice가 꼭 더 필요합니다.
그 이유에 대해 설명드리겠습니다.
왼쪽의 원 안에 예술가들은 그림을 한번씩 샀던 예술가 들 이며 그림을 샀던 순서는 상관하지 않고, visited 로 비트마스킹 형태로 나타내게 됩니다.
현재 그림을 가지고 있는 예술가는 5번 예술가 입니다. 원 안의 1, 2, 3, 4 번 예술가 중 한명에게 그림을 prePrice 원 에 구매한 상태 입니다.
이제 6번 예술가 에게 그림을 팔려고 하는 상황을 생각해 봅시다.
이때, 보통 DP 문제 처럼 cache [cur] [visited] 로 2차원 배열로 메모이제이션을 적용하게되면 문제가 발생합니다.
위의 그림에서 5번 예술가가 2번 예술가에게 그림을 살때의 가격은 10원, 4번 예술가에게 그림을 살때의 가격은 90원 이라고 해봅시다.
이때 2번 예술가에게 그림을 사던 4번 예술가 에게 그림을 사던 cache [cur] [visited] 는 동일합니다. cur 은 5번 예술가 이며 visited 는 1, 2, 3, 4 번 예술가가 그림을 구매했음을 비트마스킹으로 나타내게 되겠죠. 1111 (2진법) 일 겁니다.
하지만, 이때 6번 예술가 에게 그림을 nextPrice 인 50원에 팔면, cur, visited 가 동일함에도 cache [cur] [visited] 의 값이 달라지게 됩니다!
문제의 조건이 “전에 그림을 샀던 가격 보다 크거나 같은 가격으로 팔아야 한다.” 이기 때문이죠.
2번 예술가에게 20원에 그림을 샀으므로 6번 예술가에게 50원에 팔 수 있지만, 4번 예술가에게 90원에 산 경우 6번 예술가에게 50원에 그림을 팔 수 없습니다. 그림의 가격이 더 낮기 때문이죠.
따라서, cur 와 visited 가 같아도 longestPath() 가 prePrice 에 따라서 달라질 수 있습니다.
그러므로 보통 DP 문제처럼 문제를 정의하면 부분문제가 전의 문제의 prePrice 에 의존하게 되므로 메모이제이션이 성립하지 않게 됩니다.
그럼 어떻게 하면 될까요? 바로 알아보겠습니다.
메모이제이션 적용 방법
위에서 우리는 일반적인 DP 방법으로 메모이제이션이 불가능함 을 확인했습니다.
정의했던 부분문제가 전의 문제의 prePrice에 의존하고 있기 때문이죠.
의외로 이를 해결하는 방법은 간단합니다.
메모이제이션을 할 때 cache [cur] [visited] 대신 prePrice 를 추가한 cache [cur] [visited] [prePrice] 로 해주면 간단하게 해결됩니다.
이 문제의 핵심은, prePrice 에 따라서 부분 문제가 달라지므로, 메모이제이션을 할때 prePrice 를 추가해줘야 한다 였습니다.
바로 소스코드로 구현해 보겠습니다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define INF 987654321;
int num;
int map[16][16];
int cache[16][(1 << 17) + 1][10];
int dfs(int cur, int visited, int prePrice)
{
// 메모이제이션에 prePrice 를 추가
int& ret = cache[cur][visited][prePrice];
if (visited == (1 << num) - 1)
return ret = 1;
if (ret != 0)
return ret;
ret = 1;
for (int next = 0; next < num; next++)
{
if (visited & (1 << next))
continue;
if (next == cur)
continue;
// 가격이 더 높은 경우에만 판매한다
if (map[cur][next] >= prePrice)
ret = max(ret, dfs(next, (visited | 1 << next), map[cur][next]) + 1);
}
return ret;
}
void solve()
{
cout << dfs(0, 1, 0) << endl;
}
int main()
{
cin >> num;
for (int i = 0; i < num; i++)
{
string s;
cin >> s;
for (int j = 0; j < num; j++)
{
map[i][j] = s[j] - '0';
}
}
solve();
return 0;
}
문제의 접근방식과 아이디어를 그대로 소스코드로 구현하였습니다.
문제풀이 후기
이 문제는 백준 2098번 외판원 순회 를 해결하신 분 이라면 어렵지 않게 접근하실수 있었을 거라고 생각합니다.
저의 경우 다이나믹 프로그래밍 문제를 알고리즘 문제해결전략, 일명 종만북 으로 공부하고 있었는데 많은 도움을 받은 것 같습니다.
하지만, 부분문제를 정의할때 전의 문제에 의존한다면 매개변수를 바꿔야 한다는 점이 어려웠던 문제입니다.
알고리즘 문제해결전략 의 동적 계획법 테크닉 파트 (9장) 에서 위와같이 일반적인 동적 계획법으로 해결할수 없어서 매개변수를 바꿔야 하는 경우에 대한 설명이 자세히 나오므로, 책으로 공부하셔도 좋을 것 같습니다.
많은 도움이 되었길 바랍니다. 감사합니다.