6. BFS - 어린이날(childrenday) 문제

이 문제는 언뜻봐서는 그래프와 관련없어 보인다.

하지만 장난감의 수를 한자리씩 조합해 나가는 과정에서 그래프의 최단경로 알고리즘을 활용할 수 있다.

우선 문제에서 요구한 조건은 다음과 같다.

1. n+m 이상이어야 한다. (n명의 아이들에게 하나씩 나누어주고, m명의 아이들에게 하나씩 더 나누어주는 경우)

2. n으로 나눈 나머지가 m이어야 한다.

( n명의 아이들에게 k개씩 나누어주고, m명의 아이들에게 하나씩 더 나누어주기 때문에 n*k+m의 형태가 된다)

3. d에 포함된 숫자들로만 이루어져 있어야 한다.

앞에서 웨브바짐 문제에서 활용하였던 나머지 연산의 분배법칙을 다시 활용할 수 있다.

3번 조건을 만족하는 장난감의 수를 한자리씩 만들어갈때, 지금까지 만든 수를 c라고 하면

c를 n으로 나눈 나머지를 알면, c의 뒤에 숫자 x를 붙인 결과값을 n으로 나눈 나머지도 구할 수 있다.

((c mod n) * 10 + x) mod n = (c * 10 +x) mod n 이기 때문이다.

즉, c를 n으로 나눈 나머지에 10을 곱해 x를 더한 값을 n으로 나눈 나머지를 구하면 된다.

그러면 문제를 해결하기 위해 장난감의 개수에 대해 d에 포함된 숫자들 중 하나씩 조합해가면서 n으로 나눈 나머지를 계산하면된다.

그리고 n+m 이상인 최소 장난감의 개수를 구하면 된다.

문제를 해결하기 위해 c를 n으로 나눈 나머지를 정점으로 갖는 그래프를 만들도록 한다.

따라서 그래프는 0 부터 n-1 까지의 정점을 가지고 있다.

각 간선들은 현재 c에 숫자 x를 붙였을 때 n으로 나눈 나머지값의 정점으로 향하도록 하고, x로 번호를 매긴다.

즉 각 정점으로 향하는 경로의 간선 번호를 조합하면, 해당 c의 값을 구할 수있다.

나머지가 m인 장난감의 최소 개수를 구해야 하므로, 정점 m으로 가는 최단 경로를 구해야 한다.

최단 경로일 때 나머지가 m인 장난감의 개수의 자릿수가 최소가 되기 때문이다.

단, 이때 한 정점에서 다른 정점으로 갈 때 간선이 여러개 있다면 간선의 번호가 작은 순으로 방문하도록 한다.

장난감의 개수의 자릿수가 같다면, 자릿수가 높은 자리부터 숫자가 최소여야 하기 때문이다.

그러면 이제 n+m 이상이어야 한다는 조건만 만족하면 된다.

현재 그래프에서는 각 정점에 도달했을 때 만들어진 c의 값이 n 이하 일수도 있기 때문에, n+m 이상이어야 한다는 조건을 만족하지 못한다.

이 문제를 해결하기 위해서 각 나머지 값들에 대해 정점을 두개씩 만들도록 한다.

하나는 현재까지 만든 c값이 n 미만일 경우 도달하는 정점이고, 하나는 n이상일때 도달하는 정점이다.

전자를 흰색 정점, 후자를 회색 정점이라고 하면, 우리가 찾는 경로는 흰색 0 정점에서 회색 m 정점으로 향하는 최단 경로인 것이다.

정점을 구분하기 위해 흰색 정점은 0부터 n-1 까지, 회색 정점은 n 부터 2n-1 까지로 번호 매긴다.

// 어린이날 문제를 해결하는 최단 경로 알고리즘

// 현재 here 정점에서 edge 간선을 따라갔을 때 나오는 정점의 번호

int append(int here, int edge, int n){

int there = here * 10 + edge;

if( there < n) return there;

else return there % n + n;

}

string gift(string digits, int n, int m){

sort(digits.begin(), digits.end());  // 간선의 번호를 미리 오름차순으로 정렬하면 작은 순서부터 방문할 수 있다.

vector<int> parents(2 * n, -1);  // bfs 스패닝 트리에서 각 정점의 부모

vector<int> choice(2 * n, -1);  // 각 정점과 정점의 부모가 연결된 간선의 번호

queue<int> q;

parents[0] = 0;

q.push(0);

while(!q.empty()){

int here = q.front();

q.pop();

for(int i = 0; i < digits.size(); i++){

int there = append(here, digits[i] - '0', n);

if(parents[there] == -1){

parents[there] = here;

choice[there] = digits[i] - '0';

q.push(there);

}

}

}

if(parents[n + m] == -1) return "IMPOSSIBLE";  // 회색 m 정점에 도달하지 못했으면 실패

// 회색 m 정점에서 bfs 스패닝 트리의 부모를 따라가며 흰색 0 정점까지 간선의 번호를 기록한다.

string ret;

int here = n + m;

while(parents[here] != here){

ret += char(choice[here] + '0');

here = parents[here];

}

reverse(ret.begin(), ret.end());  // 결과를 뒤집는다.

return ret;

}