#79 암호 알아내기(Topology Sort)

이번문제는 난이도 5%로 아주 쉬운 문제로 분류되어 있습니다.

아마 단순무식(Brute Force) 방법으로도 풀리는 문제로 분류되어서인 듯 합니다.

 

숫자가 많지 않기 때문에 단순하게 조건에 맞도록 배열하는 것이 가능합니다.

예를 들어서 317 236 이 있다면, 총 숫자는 5가지 숫자가 쓰였으므로 5가지 숫자를 적절하게 배열한 다음에 조건에 맞는 수열을 고르는 것입니다.

 

일단 문제를 살펴본다면 다음과 같습니다.

 

주어진 숫자가 있습니다.  예를 들어서 531278이란 숫자가 있다면요.  이 숫자를 가지고 있음을 확인하면서, 네트웍 전송상에서 원래의 숫자를 알아내기 힘들게 하기 위해서 첫번째, 세번째, 다섯번째 숫자를 보내길 요구할 수 있습니다.  그러면 517을 전송하게 됩니다.  그런데 이러한 전송이 많아지면, 그 숫자들을 바탕으로 원래의 숫자를 추측할 수 있습니다.  조건이 있다면, 숫자들을 항상 증가하는 순서로 요구한다는 것입니다.  예를 들어서 세번째, 두번째, 네번째 숫자를 보내길 요구하지 않는다는것입니다.

 

주어진 파일에는 50개의 세자리 숫자가 있고, 이 숫자는 위에서 이야기한대로 원래의 숫자가 있고, 이것을 50번정도 숫자를 추출하게 된 것이죠.  그래서 원래의 숫자를 가장 짧은 형태로 찾아야 합니다.

 

접근방법으로는 단순무식법도 있지만, 위상정렬을 이용하는 방법도 있습니다.  예를 들어서 319 680 690 이란 숫자들이 있다고 해보죠.  이것을 위상 그래프로 그려보면 다음과 같습니다.

 

Topology Sort

그러면 위의 그래프를 만족하는 것은 다양하게 나옵니다.  316980이 될 수도 있지만 368190이 될 수도 있습니다.  50개의 데이터를 이용하면 실제 진입간선이 없는 노드는 유일하게 하나 나올겁니다.  그렇지 않다면, 유일한 해가 안 되겠죠.  물론 겹치는 숫자가 있다면, 문제 난이도가 높아집니다.  제 생각에는 풀이가 불가능할 것이라고 보입니다.

 

위상정렬을 하려면, 진입간선의 수를 카운팅해야 합니다.  진입간선의 수는 겹치는 것을 제외하면서 할 필요가 있습니다.  그래야지 간단하게 풀 수 있습니다.  위의 그래프에서 180이라는 데이터가 더 있다면, 8->0 간선은 겹치게 됩니다.  그런 예외 경우를 제외하면 됩니다.

 

전, 인접행렬을 이용해서 풀었습니다.  노드의 최대 갯수가 10개이므로 인접행렬로 풀어도 부담이 적습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

 

//------------------------------------------------
//  Project Euler #79 - Passcode derivation
//    - by Aubrey Choi
//    - created at 2015-03-19
//------------------------------------------------
#include <stdio.h>
#define  FN  "p079_keylog.txt"
#define  NUM  50

int main()
{
  int count = 0, n, d;
  static char adj[10][10], r[10], v[10];

  //  read keylog file.
  FILE *fi = fopen(FN, "r");
  for( int i = 0 ; i < NUM ; i++ )
  {
    fscanf(fi, "%d", &d);
    int a = d/100, b = (d/10)%10, c = d%10;
    if( !adj[a][b] ) adj[a][b] = 1, r[b]++;
    if( !adj[b][c] ) adj[b][c] = 1, r[c]++;
    v[a]=v[b]=v[c]=1;
  }
  fclose(fi);

  printf("Ans = "); 
  for(;;)
  {
    for( n = 0 ; n < 10 ; n++ ) if( v[n] && !r[n] ) break;
    if( n == 10 ) break;
    putchar(n+'0');
    v[n]=0;
    for( int m = 0; m < 10 ; m++ ) if(adj[n][m]) r[m]--;
  }
  putchar('\n');
}