[C][백준] 5567. 결혼식 구현하기 | 깊이 제한 그래프 탐색

이 문제의 핵심은 자신의 친구, 친구의 친구만 초대하는 것이다.

즉, 나(1번 노드)를 기준으로, 2단계 이내로 연결된 친구만 초대하는 것이다.

 

그렇다면 이 문제는 그래프 탐색 알고리즘에서 깊이를 제한하는 코드를 만들면 되는 것이다.

 

문득, 궁금증이 들었다. ChatGPT에 물어볼까?

그래서 ChatGPT에 이렇게 물어보았다.

 

 

자세한 답변 분석은 다음 포스트에 하겠다

 

아무튼 이 코드를 그대로 복붙할 수는 없으니 나의 코드와 결합하여 문제에 맞게 수정하였다.

ChatGPT에서 얻은 것은 level 배열을 쓰는 모티브랄까?

 

#include <stdio.h>

#define MAX_SIZE 10005

int vertex, edge;
int table[505][505] = {0};
int visit[MAX_SIZE] = {0};
int queue[MAX_SIZE];
int level[MAX_SIZE] = {0}; // ChatGPT의 도움!
int front = 0, rear = 0;

void addEdge(int n1, int n2);
void bfs(int v, int depthLimit); // 깊이 제한

int main()
{
    scanf("%d %d", &vertex, &edge); // 동기의 수, 리스트의 길이

    for (int i = 0; i < edge; i++)
    {
        int f1, f2;
        scanf("%d %d", &f1, &f2);
        addEdge(f1, f2);
    }

    bfs(1, 2); // 1부터 bfs, 깊이 제한 2

    int cnt = 0;
    for (int i = 2; i <= vertex; i++) // 자기자신(1) 제외
    {
        if (0 < level[i])
            cnt++;
    }

    printf("%d", cnt);

    return 0;
}

void addEdge(int n1, int n2)
{
    table[n1][n2] = table[n2][n1] = 1;
}

void bfs(int v, int depthLimit)
{
    int current; // 현재 방문 노드
    queue[rear++] = v;
    visit[v] = 1;
    level[v] = 0;

    while (front < rear)
    {
        current = queue[front++];

        if (level[current] == depthLimit) // 깊이 제한: 2
        {
            continue;
        }

        for (int i = 1; i <= vertex; i++)
        {
            if (visit[i] || !table[current][i])
            {
                continue;
            }

            queue[rear++] = i;
            visit[i] = 1;
            level[i] = level[current] + 1;
        }
    }
}