백준 알고리즘 5567번 : 결혼식

링크

https://www.acmicpc.net/problem/5567

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

예제 입력 및 출력

풀이법

1. 다른 사람의 코드를 참고해서 풀었다.
2. 문제가 의도하는 것은 1(자기자신)과 연결된 노드의 갯수를 구하라는 것이었다.
3. 그래서 아래 코드에 있는 주석과 같이 구성하였다 인접행렬 방식의 그래프이면서 무방향 그래프이니 각 정점들의 관계를 입력받으면 2차원 배열 그래프상에서 1로 표기해준다.
4. 입력을 전부 받은 후 2부터(1인 자기자신은 제외되므로) 시작해서 연결이 되어 있으면, 방문 배열의 해당 인덱스 값을 1로 만들어 방문했다고 표시한다.
5. 표시가 끝났으면 해당 정점에서 연결되어 있는 정점을 찾은 뒤에 방문배열에 방문표시를 해준다.
6. 후에 반복문을 이용해서 2부터 방문배열에 방문 표시가 되어있으면 1과 연결된 것이므로 components의 숫자를 1씩 증가시키며 수행한다.

풀이 코드(C언어)

// 5567번 : 결혼식

#include <stdio.h>
#define MAX 501

int components; // 연결 요소의 개수

int graph[MAX][MAX];
int visited[MAX];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a][b] = 1;
        graph[b][a] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        if (graph[1][i]) // 연결되어 있으면
        {
            visited[i] = 1; // 방문 배열을 방문함으로 표시
            for (int j = 2; j <= n; j++)
            {
                if (graph[i][j])
                {
                    visited[j] = 1; // 연결되어 있는 노드를 방문처리
                }
            }
        }
    }
    components = 0;
    for (int i = 2; i <= n; i++) // 자기자신(1)을 제외하기 때문에 2부터 시작
    {
        if (visited[i] == 1) // 방문되어 있으면 1과 연결되어 있다는 뜻
        {
            components++; // 그러면 친구의 갯수를 1증가시킴.
        }
    }
    printf("%d\n", components);
    return 0;
}