[백준] 5567번_알고리즘_그래프_결혼식

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

5567번: 결혼식

문제

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

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

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

예제 입력 예시

6 5 1 2 1 3 3 4 2 3 4 5

만약 이렇게 입력한다면,

상근이(1)과 2는 친구,

상근이(1)과 3은 친구,

3과 4는 친구,

2와 3은 친구,

4와 5는 친구이다.

​

문제에서는 상근이의 친구, 그 친구의 친구까지가 몇 명인지를 출력하는 것을 원한다.

따라서 예시가 위와 같다면, 상근이의 친구인 2와 3, 그리고 2와 3, 3의 친구인 4까지 포함하여 2,3,4번 총 3명이다.

---

그래프

이 문제를 더 쉽게 표현하기 위해서는 그래프를 알아야 한다.

그래프란, 어떤 자료나 개념을 표현하는 정점들의 집합 V와 이들을 연결하는 간선들의 집합 E로 구성된 자료구조를 말한다.

빨간 선을 간선 edge 또는 link라고 한다. 초록 원을 정점 vertex 또는 node라고 한다.

이 그래프로 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현할 수 있다.

현실 세계의 사물의 연결 관계의 예로는 이번에 풀이할 백준 결혼식 문제이다.

추상적인 개념 간의 연결 관계의 예로는 마인드맵이 있다.

​

그래프 기본 용어

- 인접

위 그림에서 정점 1과 정점 2는 인접해있다. 또 정점 2와 4도 인접해있다.

'인접하다'라는 의미는 정점과 정점이 간선으로 연결되어 있을 때를 말한다.

​

-순환

위 그림에서 정점 1, 정점 2, 정점 3은 순환이다.

'순환'이라는 의미는 하나의 정점에서 시작하여 몇 개의 정점들을 거쳐 다시 처음의 정점으로 돌아올 수 있을 때를 말한다.

그래프의 구현 방법

1. 인접 행렬

i, j	1	2	3
1	0	1	1
2	1	0	0
3	1	0	0

위 표를 해석하면,

1과 1은 인접하지 않아 0, 1과 2는 인접하여 1, 1과 3은 인접하여 1이다.

2와 1은 인접하여 1, 2와 2는 인접하지 않아 0, 2와 3은 인접하지 않아 0이다.

3과 1은 인접하여 1, 3과 2는 인접하지 않아 0, 3과 3은 인접하지 않아 0이다.

​

코드로 표현한다면,

행렬 이름이 a이고, 행은 j, 열은 j이다.

행 i와 열 j가 인접한다면, a[i][j] = 1이고,

행 i와 열 j가 인접하지 않는다면, a[i][j] = 0이다.

​

- 장점

인접하는지, 인접하지 않은지 쉽게 확인 가능하다.

- 단점

실제로 인접한 양과 상관없이 불필요한 공간을 차지한다는 문제점이 있다.

​

2. 인접 리스트

​

리스트는 a, 정점의 수는 n이다.

a[n]에서 a[i]는 정점 i로부터 시작하는 간선에 연결된 정점을 연결하는 연결 리스트의 시작이다.

​

- 장점

실제 간선 수만큼의 공간을 사용하여 불필요한 공간을 차지하지 않는다.

- 단접

인접하는지, 인접하지 않은지 일일이 찾아야 한다.

---

코드 설명

1. call by reference

​

void connect(int& a, int& b);

​

함수의 호출 방식에는 call by reference와 call by value가 있다.

call by value는 함수가 호출될 때, 메모리에 별도의 임시 공간이 생성된다. 따라서 함수에서 인자의 값이 변경되어도 원래 변수의 값은 변경되지 않는다.

call by reference는 함수가 호출될 때, 메모리에 별도의 임시 공간이 생성되지 않고 원래 있던 메모리에 덮어쓴다. 따라서 함수에서 인자의 값이 변경되면, 다른 함수에서도 그 인자의 값이 모두 변경된다.

​

2. 인접 행렬

​

cin >> a >> b;

friends[a][b] = 1;

friends[b][a] = 1;

​

입력받은 a와 b는 연결되어 있다는 의미이므로 friends 행렬에 1을 담는다.

마찬가지로 입력받은 b와 a도 연결되어 있으므로 friends 행렬에 1을 담는다.

​

3.

​

if (check[i] == 1)

connectedCount++;

​

인접한다면 connectedCount를 1을 더한다.​

​

4.

​

for (int a = 2; a <= n; a++)

​

1은 상근이므로, 2부터 n까지 반복한다.

​

5.

​

if (friends[1][a])

{

check[a] = 1;

for (int b = 2; b <= n; b++)

{

if (friends[a][b] == 1) check[b] = 1;

}

}

​

만약 1(상근이)와 a가 연결되어 있으면, check 배열의 a 번 째 index에 1을 담는다.

그 후, a와 연결된 정점 b가 있다면 check 배열 b 번 째 index에 1을 담는다.

​

6.

​

for (int i = 2; i <= n; i++)

{

if (check[i]) connectedCount++;

}

​

check의 i 번 째 index가 1이면 1은 true라는 의미를 가지고 있으므로, if 문을 실행한다.

connectedCount는 1과 연결되어 있는 정점의 수를 의미한다.

코드

#include<iostream>
using namespace std;

int n, m, a, b, connectedCount = 0;
int friends[501][501];
int check[501];

void connect(int& a, int& b);

int main()
{
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		friends[a][b] = 1;
		friends[b][a] = 1;
	}

	connect(a, b);

	for (int i = 2; i <= n; i++)
	{
		if (check[i]) connectedCount++;
	}

	cout << connectedCount << endl;
}

void connect(int& a, int& b)
{
	for (int a = 2; a <= n; a++)
	{
		if (friends[1][a])
		{
			check[a] = 1;
			for (int b = 2; b <= n; b++)
			{
				if (friends[a][b] == 1) check[b] = 1;
			}
		}
	}
}

 

​