[알고스팟] CHILDRENDAY - 어린이날 (C++, BFS)

문제

 

https://algospot.com/judge/problem/read/CHILDRENDAY

 

풀이

 

종만북 난이도: 상!!

 

상당히 어려운 BFS 문제이다.

문제를 보면 생각나는 간단한 풀이는 자릿수를 사용해 모든 경우의 수를 생성해 보는 것이지만 당연히 시간 초과가 발생한다.

 

일단 다음의 두 가지 조건만을 만족하는 최소 자연수 C를 구하는 방법을 생각해보자.

(어린이의 수를 children_num, 욕심쟁이의 수를 greedy_num이라고 하자.)

 

• C를 children_num으로 나눈 나머지는 greedy_num이다.
• C는 d에 포함된 숫자들로만 구성된다.

 

이를 구하기 위해서 나머지 연산의 분배 법칙을 이용하자.

 

(A*B) mod n = ((A mod n) * (B mod n)) mod n

 

따라서 다음이 성립한다.

((c mod n)*10 + k) mod n = (c*10 + k) mod n

 

이제 그래프의 정점의 수 자체가 아닌 n으로 나눈 나머지로 나타낼 수 있게 된다.

만약 이번에 구한 수의 나머지가 A였다면 다음 수의 나머지는 (A*10 + k) mod n 가 된다.

 

예를 들어 A가 5이고 n이 7이며 사용 가능한 수가 1과 2라면 그래프는 다음과 같이 연결된다.

 

예제의 입력인

1(사용 가능한 수)  7(어린이 수)  0(욕심쟁이 수)에 대하여 그래프를 나타내면 다음과 같다.

 

우리는 0번 정점에서 시작하여 나머지(m)가 0이 되는 정점까지의 경로(어떤 수를 선택하는지)를 찾아야 한다.

BFS에서는 너비 우선의 탐색을 하므로 자연스럽게 최단 경로를 찾을 수 있다.

이 예제에서는 숫자 1만을 선택할 수 있으므로 모든 정점이 단 하나의 간선만을 갖는다.

 

문제는 0에서 시작하여 0에 도착하는 최단 경로는 어떤 정점으로도 이동하지 않는 것이다.

 

이제 세 번째 조건을 고려해보자.

• C는 children_num + greedy_num 이상이어야 한다.

0은 children_num + greedy_num인 7보다 작기 때문에 답이 될 수 없다.

따라서 나머지를 나타내는 정점을 두 개씩 생성합니다.

하나는 n미만의 정점, 하나는 n이상의 정점으로 n 이상의 정점들만 정답이 될 가능성을 가집니다.

이러한 정점들 중에서 m의 값을 가리키는 정점을 찾아 줍시다.

 

이처럼 두 가지 정점을 표현하기 위해 0~n-1 사이의 수 a에 대하여

a는 n미만의 a정점을, a+n은 n이상의 a정점을 가리키는 인덱스 값으로 사용합니다.

 

이 경우 기존의 정점의 수 n과 사용 가능 한 수의 개수 d(간선의 수)는

두 배씩 늘어나 BFS의 시간 복잡도는 O(2*n*d)가 됩니다.

 

이 조건으로 다시 예제의 입력을 그래프로 나타내면 다음과 같습니다.

 

여기서 최초 시작점인 n미만의 0 정점에서 BFS를 진행하면 다음과 같이 n이상의 0에 도달한다.

여기서 거친 각각의 간선은 어떤 수를 선택했는지를 나타내고 간선의 역순이 조건을 만족하는 최솟값 C가 된다.

이를 표현하기 위해 각 정점의 부모 정점을 저장하는 parent배열과 어떤 수를 선택했는지 저장한 choice 배열을 사용한다.

 

 

int Append(int here, int edge, int mod){
  int there = here*10 + edge;
  if(there >=mod)
    return mod + there %mod;  // n이상의 경우는 mod를 더해 주어 표현해 n이하와 구분하자
  return there % mod;
}
 
string Gifts(const string& digit_str, int children_num,int greedy_num){
  vector<int> digit_list(digit_str.size());
 
  for(int i=0; i<digit_str.size() ; ++i)
    digit_list[i] = digit_str[i] - '0';
 
  sort(digit_list.begin(), digit_list.end());
 
  vector<int> parent(2*children_num, -1), choice(2*children_num, -1);
  queue<int> que;
 
  parent[0] = 0;
  que.push(0);
 
  int here,there;
  while(!que.empty()){
    here = que.front();
    que.pop();
 
    for(int i=0; i<digit_list.size() ; ++i){
      there = Append(here , digit_list[i], children_num);
 
      if(parent[there] == -1){
        parent[there] = here;
        choice[there] = digit_list[i];
        que.push(there);
      }
    }
 
  }
 
  if(parent[children_num+ greedy_num] == -1)  // 정답에 도달하지 못한 경우
    return "IMPOSSIBLE";
 
  string ret;
  here = children_num+ greedy_num;
  while(parent[here] != here){  //0으로 도달하여 끝난 경우
    ret += char('0' + choice[here]);
    here = parent[here];
  }
 
  reverse(ret.begin(), ret.end());
  return ret;
}

 

 

참고 서적: 알고리즘 문제 해결 전략(구종만 저)

 

코드