[백준 10451번] C++ 순열 사이클(BFS)

문제

 

문제 분석

flood fill 유형이다. 연결되어 있는 뭉텅이의 개수를 세는 유형인데 형태만 바뀌어서 출제된 것이다.

위 행렬을 참고하면 첫 번째 1 3 의 의미는 1번 노드는 3번 노드와 연결이 되어 있다는 의미이다. 두 번째 2 2의 의미는 2번노드와 2번 노드가 연결되어 있다는 것이다.

위 행렬의 연결 상태를 나타낸 것이 위 그림과 같은 것이다.

우리는 이 뭉텅이의 개수를 세어야 한다. 위 그림에서는 3개이므로 정답은 3이다.

 

이 뭉텅이의 개수를 찾기 위해 DFS나 BFS 탐색을 한다.

- 1~n까지 돌면서 아직 방문하지 않은 노드를 찾으면 그 노드를 첫 번째 노드로 DFS/BFS 탐색을 실행한다.

- 최종적으로 1~n까지 돌면서 DFS/BFS 탐색을 몇 번 돌았는지가 우리가 찾고자 하는 뭉텅이의 개수가 될 것이다.

 

정답 코드

- 문제 분석을 바탕으로 정답 코드를 구현한다.

- 레퍼런스 변수를 활용하였다. vector<pair<int, int>>& p 처럼 p를 참조하였다.

 

#include <iostream>
#include <vector> // pair
#include <queue>
#define MAX_N 1001
using namespace std;
int visited[MAX_N];

void bfs(int start_node, int start_next_node, vector<pair<int, int>>& p) {
	queue<pair<int,int>> q;

	// 초기 노드 방문처리
	q.push({ start_node, start_next_node });
	visited[start_node] = 1;

	while (!q.empty()) {
		int cur_node = q.front().first;
		int next_node = q.front().second;
		q.pop();
		// 이전에 방문한 적이 있다면 건너뛴다.
		if (visited[next_node] != 0) continue;

		// 다음 노드 조건 만족 시 방문 처리
		q.push({ p[next_node].first, p[next_node].second});
		visited[p[next_node].first] = 1;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		vector<pair<int, int>> p;
		fill(visited, visited + MAX_N, 0); // 전부 0으로 초기화
		int n;
		cin >> n;
		for (int cur = 0; cur < n; cur++) {
			int next;
			cin >> next;
			p.push_back(make_pair(cur, next-1));
		}

		// 1~n까지 돌면서 bfs 탐색
		int ans = 0;
		for (int j = 0; j < n; j++) {
			if (visited[p[j].first] == 0) {
				bfs(p[j].first, p[j].second, p);
				ans++;
			}
		}
		cout << ans << "\n";
	}

	return 0;
}