[BAEKJOON] 백준 5567: 결혼식 (C#)

문제 링크

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도 친구관계이다. 

 

 

출력

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

 

 

 

통과한 답안

namespace _5567
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());

            List<int>[] connections = new List<int>[n + 1];
            for (int i = 0; i <= n; i++)
            {
                connections[i] = new List<int>();
            }

            for (int i = 0; i < m; i++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                int a = int.Parse(inputs[0]);
                int b = int.Parse(inputs[1]);
                connections[a].Add(b);
                connections[b].Add(a);
            }

            bool[] invited = new bool[n + 1];
            int cnt = 0;

            foreach (int friend in connections[1])
            {
                if (!invited[friend])
                {
                    invited[friend] = true;
                    cnt++;
                }

                foreach (int friendFriend in connections[friend])
                {
                    if (!invited[friendFriend] && friendFriend != 1)
                    {
                        invited[friendFriend] = true;
                        cnt++;
                    }
                }
            }

            Console.WriteLine(cnt);
        }
    }
}

 

n명의 동기의 수와 m개의 친구 관계가 주어졌을 때,

1번과 친구이거나 친구의 친구인 사람의 수를 구하는 문제이다.

 

List를 이용하여 각각의 동기의 친구 관계를 입력 받은 후에

초대 대상이 될 bool 배열을 선언한다.

 

1번의 친구들에 대해서 초대하지 않은 친구라면 bool 값을 바꿔서 초대한 상태로 변경하고

그 친구의 친구 중에서 1번이 아닌 친구들 중에서 초대하지 않은 친구라면

bool 값을 바꿔서 초대한 상태로 변경한다.

초대한 친구들을 카운트 하는 것으로 문제를 해결할 수 있다.

 

1번의 친구만 초대하는 문제라면 처음의 입력 받는 상태에서 해결할 수 있는 문제지만,

친구의 친구까지 초대하는 문제로써 List와 배열을 이용하여 1번의 친구이면서

초대받지 않은 상태인 친구의 친구를 추가하는 부분이 포인트인 문제였다.