[백준 BOJ] 5567번 결혼식 (C++/cpp)

문제 설명

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

5567번: 결혼식

 

접근 방법 - 너비 우선 탐색(BFS) 이용한 연산 문제

백준의 5567번 문제는 그래프 탐색 연산을 이용하여 해결해야하는 문제이다.

해당 문제는, 입력받은 동기들의 관계를 통해 상근이가 결혼식에 초대할 인원의 수를 구하여 출력해야하는 문제이다.

여기서 상근이는 자신의 친구와 친구의 친구까지만 자신의 결혼식에 초대한다는 조건이, 문제에 제시되어있다.

따라서 굳이 DFS나 BFS를 사용할 필요가 없는 문제이다. 하지만 필자는 실패해서 BFS 설명 위주로 하려 한다.

필자가 작성한 풀이대로 해결을 해도 되지만, 한번은 되도록 DFS나 BFS를 사용하지 않고 풀어보는 것도 좋을 것이다.

해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 동기들의 관계를 입력받을 배열(list)을 전역 변수로 미리 선언해둔다.

그와 동시에, 이미 카운트된 동기인지에 대한 여부를 파악하기 위해 visit 배열도 전역 변수로 미리 선언해둔다.

 

2) 동기의 수(n), list의 총 개수(m)를 순차적으로 입력받는다.

 

3) 상근이 본인은 카운트되지 않도록 visit[1]의 값을 1로 즉시 변경한다.

 

4) 초대할 동기들의 수를 저장할 변수(cnt)를 0으로 초기화하여 선언해둔다.

 

5) BFS 연산을 하기 위해, int형 타입인 큐(q)를 선언해둔다.

 

6) m의 크기만큼 반복문을 실행해 아래의 연산을 취한다.

- list의 값을 한 쌍씩 입력받는다.
- 만일 한 쌍의 list 중 하나의 값이 1이라면, 다른 값은 상근이의 친구임을 뜻한다.

따라서 이 경우엔, q에 해당 값을 push하고, 이를 인덱스로 갖는 visit의 값을 1로 변경한다.

또한, 해당 동기는 결혼식에 초대할 인원이니 cnt에 1을 더하도록 한다.

 

7) 위의 입력과 연산이 모두 끝났다면, q가 빌 때까지 반복문을 돌려 아래의 연산을 취한다.

- 변수 num을 선언하여 q의 front 값을 저장하도록 한다.

- 반복문을 통해 list의 값들을 탐색한다.

만일, 한 쌍의 list 중 하나의 값이 현재 num 값과 동일하다면, 다른 값은 상근이의 친구의 친구임을 뜻한다.

따라서 이 경우엔, 해당 값을 인덱스로 갖는 visit의 값을 1로 변경하고 cnt에 1을 더하도록 한다.

(상근이의 친구와 그 친구의 친구까지만 초대하기 때문에, push 연산은 수행하지 않도록 한다.)

- 현재 num에 대한 연산이 끝났다면, q에 대하여 pop 연산을 취하도록 한다.

 

8) 모든 연산이 끝났다면, 최종적으로 저장된 cnt의 값을 출력한 뒤 실행 종료한다.

 

후기

위에서도 말하였지만 BFS 및 DFS를 사용하지 않고 해결을 시도해본 결과, 필자는 실패하였었다.

그리고 이 글을 쓰면서 실패한 코드를 다시 살펴보니 어떤 경우에 에러가 생기는지 알게 되었다.

아마 추후에, 해당 문제에 대하여 DFS 및 BFS를 사용하지 않은 코드를 게시하지 않을까 싶다.

우선은 먼저 그 방법으로 풀어봐야겠지만 말이다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;

//백준 5567번 코드
int list[10001][2];
int visit[501];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	visit[1] = 1;

	int cnt = 0;
	queue<int> q;
	for (int i = 0; i < m; i++) {
		cin >> list[i][0] >> list[i][1];
		if (list[i][0] == 1) { q.push(list[i][1]); visit[list[i][1]] = 1; cnt++; }
		if (list[i][1] == 1) { q.push(list[i][0]); visit[list[i][0]] = 1; cnt++; }
	}

	while (!q.empty()) {
		int num = q.front();
		for (int i = 0; i < m; i++) {
			if (list[i][0] == num && visit[list[i][1]] == 0) {
				visit[list[i][1]] = 1;
				cnt++;
			}
			if (list[i][1] == num && visit[list[i][0]] == 0) {
				visit[list[i][0]] = 1;
				cnt++;
			}
		}
		q.pop();
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.07.20 백준 5567번 문제 제출 결과)