[SwExpertAcademy] 비밀

문제 출처 :

https://www.swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyoNqAiQDFAW4#

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

2. define 함수 주의사항

문제에서 요구하는 것은 현재 정점에서 나가는 간선의 수가 몇개인지를 구하는 것과

이 그래프에서 각정점끼리 이을 수 있는 최대 길이를 구하라는 것이다.

첫번째 것은 outDegree를 찾으면 되고

두번째 것은 1번노드부터 n번노드까지 돌며 모두 순회해보면 된다.(n이 작기에 가능)

이 문제와는 무관하지만, define을 잘못쓰면 나타나는 오류도 첨부하고자 한다.

define max를 이용하는 방법이 잘못된 TLE 코드이다.

ret = max(ret, solve(next) + 1);

이렇게 쓰게되면 define에 의해 매핑이 되어

ret = ret > solve(next) + 1 ? ret : solve(next);가 되어

결국 solve를 두번하는 현상이 나타나게 된다.

이는 이 문제에서만이 아닌 define 매크로를 이용할 때 항상 조심하자.

소스 코드 : 

AC 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #define max(a,b)(a > b ? a : b)     bool visit[15]; int arr[15][15]; int outDegree[15]; int n, k; int ret; void solve(int here, int cnt) {     ret = max(ret, cnt);       for (int i = 1; i <= n; i++) {         if (!arr[here][i] || visit[i])             continue;         visit[i] = true;         solve(i, cnt + 1);         visit[i] = false;     } } int main() {     int tCase;     scanf("%d", &tCase);       for (int tc = 1; tc <= tCase; tc++) {         ret = 0;         for (int i = 0; i < 15; i++) {             visit[i] = outDegree[i] = 0;             for (int j = 0; j < 15; j++)                 arr[i][j] = 0;         }            scanf("%d %d", &n, &k);           for (int i = 0; i < k; i++) {             int prev = -1;             int m;             scanf("%d", &m);             for (int j = 0; j < m; j++) {                 int cur;                 scanf("%d", &cur);                   if (prev != -1 && !arr[prev][cur]) {                     arr[prev][cur] = 1;                     outDegree[prev]++;                 }                   prev = cur;             }         }           printf("#%d ", tc);         for (int i = 1; i <= n; i++)             printf("%d ", outDegree[i]);           for (int i = 1; i <= n; i++) {             for (int j = 0; j < 15; j++)                 visit[j] = 0;             visit[i] = true;             solve(i, 1);         }           printf("%d\n", ret);     }     return 0; }     Colored by Color Scripter

cs

TLE 코드 

 
#include <iostream>
#define max(a,b)(a > b ? a : b)
 
class vector {
public:
    int capacity, sz;
    int *vc;
 
    vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~vector() {
        delete[] vc;
    }
    void push_back(int val) {
        if (capacity == sz) {
            capacity *= 2;
            int *tmp = new int[capacity];
            for (int i = 0; i < sz; i++)
                tmp[i] = vc[i];
            delete[] vc;
            vc = tmp;
        }
        vc[sz++] = val;
    }
    int size() { return sz; }
    bool empty() { return !sz; }
    void clear() { sz = 0; }
    int &operator[](int i) { return vc[i]; }
};
 
bool visit[15];
vector vc[15];
bool overlap[15][15];
 
int solve(int here) {
    int ret = 0;
 
    for (int i = 0; i < vc[here].size(); i++) {
        int next = vc[here][i];
        if (visit[next])
            continue;
 
        visit[next] = true;
        ret = max(ret, solve(next) + 1);
        visit[next] = false;
    }
    return ret;
}
int main() {
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        for (int i = 0; i < 15; i++) {
            visit[i] = false;
            vc[i].clear();
            for (int j = 0; j < 15; j++)
                overlap[i][j] = 0;
        }
 
        int n, k;
        scanf("%d %d", &n, &k);
 
        for (int i = 0; i < k; i++) {
            int prev = -1;
            int m;
            scanf("%d", &m);
            for (int j = 0; j < m; j++) {
                int cur;
                scanf("%d", &cur);
 
                if (prev != -1 && !overlap[prev][cur]) {
                    printf("form :: %d to :: %d\n", prev, cur);
                    vc[prev].push_back(cur);
                    overlap[prev][cur] = true;
                }
 
                prev = cur;
            }
        }
 
        int ans = -1;
        printf("#%d ", tc);
        for (int i = 1; i <= n; i++) {
            printf("%d ", vc[i].size());
 
            for (int j = 0; j < 15; j++)
                visit[j] = false;
 
            visit[i] = true;
            ans = max(ans, solve(i));
            visit[i] = false;
        }
 
        printf("%d\n", ans + 1);
    }
    return 0;
}