5567 결혼식

그래프 탐색 문제

친구의 친구까지만 결혼식에 초대한다

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

1. 문제

---

간단 설명

친구의 친구에게만 청첩장을 보낸다

친구의 친구의 친구는 상도덕이 없어보이므로 보내지 않음

즉, 2단계까지 연결된 노드를 찾는 문제

2. 문제 분석

---

필요변수

동기 수 int n (최대 500명)

관계를 저장할 그래프 int map[501][501](연결리스트로 해도 되지만, 배열로 선언)

리스트의 길이 int m (최대 10000개)

m개의 친구 관계 a, b가 주어진다

주의점

• 다행히 친구 관계는 쌍방 관계라 한쪽만 친구라고 생각하는 경우는 없음. 양뱡향 리스트 이용

알고리즘

1. BFS 이용 ```
2. n, m 입력받기
3. m개의 간선 정보를 받아 그래프 채우기
4. 큐에 1번 상근이를 넣는다
5. 그래프 정보를 바탕으로 BFS 시작 4-1. 큐에서 맨 앞 노드를 꺼낸다 4-2. 현재 레벨이 2를 초과한다면 패스한다 (친구의 친구를 넘음) 4-3. 이미 청첩장을 보낸 경우라면 패스한다 4-4. 친구가 아니라면 패스한다 4-5. 위 조건들을 통과했다면, 청첩장을 보내고(visited[i] = 1), 큐에 level + 1해서 넣는다

6. BFS 종료 후, vistied가 체크된 노드들의 개수를 확인후 개수를 출력한다 ```

7. DFS 이용 ```
8. 입력받기
9. DFS로 연결된 그래프들을 2단계 까지 체크한다 ```
   • DFS는 항상 말로 표현하기가 어려움…

3. 소스코드

---

1. BFS 이용 ```cpp #include #include

using namespace std;

#define MAX 501

int n, m; int map[MAX][MAX]; // 1 ~ n개 사용 int visited[MAX];

struct node { int num; int level; };

int main() { freopen_s(new FILE*, “input.txt”, “r”, stdin); cin » n » m;

// m개 입력
for (int i = 0; i < m; i++) {
	int start, end;
	cin >> start >> end;
	map[start][end] = 1; // 양방향 노드
	map[end][start] = 1;
}

visited[1] = 1; // 상근이
queue<node> qu;
qu.push({ 1, 0 });

while (!qu.empty()) {
	node now = qu.front();
	qu.pop();

	for (int i = 2; i <= n; i++) {
		if (now.level >= 2) continue; // 친구의 친구까지만 살펴봄
		if (visited[i] == 1) continue; // 이미 초대한 경우
		if (map[now.num][i] == 0) continue; // 친구가 아닌 경우

		visited[i] = 1;
		qu.push({ i, now.level + 1 });
	}
}

int cnt = 0;
for (int i = 2; i <= n; i++) {
	if (visited[i] == 1) {
		cnt++;
	}
}
cout << cnt;
return 0; } ```

1. DFS 이용 ```cpp #include #include

using namespace std;

int n, m; vector< vector > map; int visited[501];

void DFS(int level, int now) { if (level >= 2) { return; }

for (int i = 0; i < map[now].size(); i++) {
	int next = map[now][i];
	visited[next] = 1; // 방문체크했다고 continue가 아니라, 일단 더 들어가본다
	DFS(level + 1, next);
} }

int main() { freopen_s(new FILE*, “input.txt”, “r”, stdin); cin » n » m; map.resize(n+1);

for (int i = 0; i < m; i++) {
	int start, end;
	cin >> start >> end;
	map[start].push_back(end);
	map[end].push_back(start);
}

visited[1] = 1;
DFS(0, 1);

int cnt = 0;
for (int i = 2; i <= n; i++) {
	if (visited[i] == 1)
		cnt++;
}

cout << cnt;
return 0; } ```