5-1 비밀

어떤 비밀 이야기. 앤명의 아이들 유치원, 선생님 아이들 비밀 이야기

어떻게 전달되었는지에 대한 정보 주어짐. 이 정보로 알 수 있는 각 아이들이 친하다고 생각하는 친구들의 수를 구함

어떤 비밀이 전달될 수 있는 가장 긴 길이도 구하자

에이가 비를 친하다고 생각하더라도, 비가 에이를 친하다고 생각하지 않을 수 있음을 유의. 

인풋에 대한 정보 오케이

#include <stdio.h>

#define MAX_N 10
#define MAX_K 30

int N, K, M;
int INPUT[MAX_K][MAX_N + 1];

int MAP[MAX_N + 1][MAX_N + 1];
int FRIEND[MAX_N + 1];
int visit[MAX_N + 1];
int result;
int path[MAX_N + 1];

#define MAX_VERTEX 31

void depthFirstSearch(int v, int depth)
{
    int i;
    int temp;

    if (result == N) return;
    //if (visit[v]) return;

    path[depth] = v;

    for (i = 1; i <= N; i++)
    {
        if (v == i) continue;

        if (MAP[v][i])
        {
            if (visit[i]) continue;

            visit[i] = 1;

            temp = depth + 1;
            path[temp] = i;
#if 0
            for (int j = 0; j <= temp; j++) {
                printf("-> %d ", path[j]);
            }
            printf("\n");
#endif
            temp = 0;
            for (int j = 1; j <= N; j++) {
                if (visit[j]) temp++;
            }
            if (visit[path[0]] == 0) temp++;

            if (result < temp) result = temp;

            depthFirstSearch(i, depth + 1);

            visit[i] = 0;
        }
    }
}

void print_map(void) {
    printf("\n");

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            printf("%d ", MAP[i][j]);
        }
        printf("\n");
    }
}

int Init(void)
{
    result = 0;
    for (int i = 0; i <= N; i++) {
        FRIEND[i] = 0;
        visit[i] = 0;
        for (int j = 0; j <= N; j++) {
            MAP[i][j] = 0;
        }
    }

    // 행렬로 만들며, 계산까지
    for (int i = 0; i < K; i++) {
        // 자기자신의 경우의 수를 체크해야함
        if (INPUT[i][0] == 1) MAP[INPUT[i][1]][INPUT[i][1]] = 1;

        for (int j = 1; j < INPUT[i][0]; j++) {
            MAP[INPUT[i][j]][INPUT[i][j + 1]] = 1;
        }
    }

    //print_map();

    return 0;
}

int Algoritm(void)
{
    // 각 아이이가 친하다고 하는 친구들의 수
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (MAP[i][j] == 0 || i == j) continue;
            FRIEND[i]++;
        }
    }

#if 1
    // 모든 경로를 검색
    for (int i = 1; i <= N; i++) {
        depthFirstSearch(i, 0);
    }
#else
    // 친구가 있는 수에서어 행렬에서 0 의숫자를 세고 + 1을 해준다?

    result = 1;
    for (int i = 1; i <= N; i++) {
        if (FRIEND[i]) result++;
    }
    if (result > N) result = N;

#endif


    return 0;
}
int Result(void)
{
    for (int i = 1; i <= N; i++) {
        printf("%d ", FRIEND[i]);
    }
    printf("%d\n", result);
    return 0;
}
int Solve(void)
{
    Init();
    Algoritm();
    Result();
    return 0;
}

int main(void)
{
    int test_case;
    int T;
    int from, to;

    freopen("test.txt", "r", stdin);
    setbuf(stdout, NULL);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d %d", &N, &K);

        for (int i = 0; i < K; i++) {
            scanf("%d", &M);
            INPUT[i][0] = M;
            for (int j = 1; j <= M; j++) {
                scanf("%d", &INPUT[i][j]);
            }
        }
        printf("#%d ", test_case);
        Solve();
    }
    return 0; //정상종료시 반드시 0을 리턴해야 합니다.
}

- 그래프 형식으로 만들기
- 트리인가
- 이 문제 풀이를 위해서 사용된 2차원 배열의 갯수 5개임
- 트리 기초 문제를 풀고 올 것