[ 백준 BOJ / c++ ] 5567번 결혼식

🤔 문제

 

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

---

👀 접근 방식

두 페어를 입력 받는 것을 보자마자 그래프 탐색 기법을 이용하려고 하였다. 하지만 친구의 친구까지만 찾으면 되기때문에 2중 for문으로 정답을 구하였다.

 

1. 친구들의 관계를 벡터에 담는다. 
2. 상근이의 번호를 1번이므로, 1번 벡터의 크기( 상근이의 친구 수)를 구한다.
3. 1번 벡터의 크기가 0일시, 친구가 없다는 뜻이므로(ㅠㅠ) 0을 출력한다.
4. 1번 벡터의 크기 1보다 클 시, 상근이의 친구들과 친구의 친구를 visit를 활용해 탐색한다. 

---

💻 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

vector<int> manNumber[501];
int visit[501];
int n, m;

int main()
{ 
	// n, m 입력
	cin >> n >> m;

	// 친구 관계 업데이트 쌍방향 관계이므로 a 와 b 둘다 추가
	int a, b;

	for (int i = 1; i <= m; ++i)
	{
		cin >> a >> b;
		manNumber[a].push_back(b);
		manNumber[b].push_back(a);
	}

	// 1번이 비어있다는 것은 친구가 없다는 뜻이므로 0 출력
	if (manNumber[1].empty())
	{
		cout << 0;
	}
	else {

		// 정답을 출력할 answer 선언과 1번(본인)은 방문처리
		int answer = 0;

		visit[1] = 1;
		
		// 1번의 친구에 대해 반복
		for (int i = 0; i < manNumber[1].size(); ++i)
		{
			// 1번 친구의 번호를 targetNumber에 담음 
			int targetNumber = manNumber[1][i];

			// targetNumber 미방문시 방문처리 후 answer 증가
			if (visit[targetNumber] != 1)
			{
				visit[targetNumber] = 1;
				answer++;
			}

			// targetNumber의 친구 개수에 대해 반복
			for (int j = 0; j < manNumber[targetNumber].size(); ++j)
			{
				// targetNumber의 친구번호를 friendNumber에 저장
				int friendNumber = manNumber[targetNumber][j];

				//freindNumber 미방문시 방문처리후 answer 1증가
				if (visit[friendNumber] != 1)
				{
					visit[friendNumber] = 1;
					answer++;
				}
			}
		}

		// 출력
		cout << answer;
	}

	return 0;
}