백준 알고리즘 5567. 결혼식

빰빠빠바~ 빰빠빠바~

화려한 음악소리와 함께 결혼식이 시작되었습니다.

​

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

5567번: 결혼식

상근이라는 친구가 결혼식에 친구도 초대하고 친구의 친구까지는 초대할 생각을 가지고 있군요.

하지만 친구의 친구의 친구처럼 3번 건너서는 너무 모르는 사람이기 때문에 초대하지 않을 생각입니다.

​

상근이가 학급에서 번호가 1번이고 몇번과 몇번이 친구라는 명단을 안다는 가정하에,

친구 또는 친구의 친구 명단을 확보해서, 총 초대할 친구를 알아맞추는 것인데요.

​

크레이는 인접행렬로 풀이하였습니다.

시간복잡도 때문에 길어질거라고 하지만 뭐 이 문제는

대부분 0ms 내에 풀이가 가능한 문제인 듯 합니다 :)

​

소스보다는 이론 위주로 설명드립니다 :)

서로 친구가 다음과 같다는 가정하에

​

1 2

1 3

3 4

2 3

4 5

​

XY축에 대해 아래와 같이 표를 그립니다.

예제 문제는 6번까지이지만 6번은 보기에서 안 나와 생략하였습니다.

그리고 나서, 친구 관계 위치에 O 를 표시합니다. 가로 세로 모두 표시합니다.

 

여기서 상근이의 친구는 아래와 같습니다.

빨간색으로 표시한 부분이지요.

 

그리고 상근이의 친구의 친구는 아래와 같습니다. 빨간색으로 표시한 부분에서 오른쪽으로 찾아 나가면 되며

파란색으로 표시한 부분이지요.

그러면 이 색칠한 것을 모두 세면 되나요? 아닙니다 :)

자세히 보시면 빨간 3번과 파랑 3번이 겹치는 것을 보실 수 있는데요.

이 경우 한번만 세어야 합니다.

​

크레이는 단순히 한줄짜리 표를 하나 더 만들어서,

겹치는 부분 포함 빨강과 파랑색을 모두 색칠한 다음에 갯수를 세었습니다.

그러면 총 3명이 카운트가 되지요.

여기가지가 크레이의 구상 알고리즘입니다.

​

이걸 프로그래밍으로 구현하면 됩니다.

인접리스트다 인접행렬이다 여러가지 알고리즘 기법이 있는데,

크레이가 시도한 것은 인접행렬 쪽에 가깝습니다 :)

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstring>
void Result()
{
	int n=0, m=0;
	scanf("%d %d", &n, &m);

	int fmap[501][501];
	

	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			fmap[i][j]=0;
	
	for(int i=0;i<m;++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);		
		fmap[a][b]=1;
		fmap[b][a]=1;
	}

	int ff[501];
	for(int i=0;i<=500;++i)ff[i]=0;
	for(int j=2;j<=n;++j)
	{
		if(fmap[1][j]==0)continue;
		ff[j]=1;
		for(int k=2;k<=n;++k)
			if(fmap[k][j]==1) 
				ff[k]=ff[j]=1;
	}

	int tot=0;
	for(int i=1;i<=n;++i)tot+=ff[i];

	printf("%d\n", tot);
}

int main()
{
	Result();
	getchar(); getchar();
	return 0;
}