본문 바로가기
코딩과 알고리즘

백준 알고리즘 5567. 결혼식

728x90

빰빠빠바~ 빰빠빠바~

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

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

 

5567번: 결혼식

문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m

www.acmicpc.net

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

하지만 친구의 친구의 친구처럼 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;
}

728x90
반응형