[백준문제풀이] 10451 순열사이클

 

풀이 일시 : 2020-10-13

​

 

문제 :

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

1 2 3 4 5 6 7 8

3 2 7 8 1 4 5 6

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

1 … i … n

π1 … πi … πn 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

​

​

입력 :

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

ex)

2

8

3 2 7 8 1 4 5 6

10

2 1 3 4 5 6 7 9 10 8

​

​

출력 :

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

ex)

3

7

​

​

풀이 :

dfs, 또는 bfs로 풀이가능하다. 그래프에 연결된 인자가 다시 자신에게로 돌아오면 순열사이클로 볼 수 있다. visit을 true로 만들어주고 count를 +1 해 주어 순열 사이클의 갯수를 구할 수 있다.

memset을 이용하여 테스트케이스마다 초기화해준다.

 

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색

 

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define MAX 1001
using namespace std;

vector <int> v[MAX];
int visit[MAX];

void bfs(int x) {
	queue<int>q;
	q.push(x);
	visit[x] = true;
	while (!q.empty()) {
		int ex = q.front();
		q.pop();
		for (int i = 0; i < v[ex].size(); i++) {
			int z = v[ex][i];
			if (visit[z] == 0) {
				visit[z] = true;
				q.push(z);
			}
			else if (z == x) {
				visit[z] = true;
			}
		}
	}
}

int main() {
	int T, N;
	int count=0;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> N;
		for (int j = 1; j <= N; j++) {
			int x;
			cin >> x;
			v[j].push_back(x);
		}
		for (int i = 1; i <= N; i++) { //순열사이클이 몇개인지 테스트한다. 모든 노드를 번갈아가며 검사
			if (!visit[i]) {
				bfs(i);
				count++;
			}
		}
		printf("%d\n", count);
		//초기화
		for (int i = 1; i <= N; i++) {
			v[i].clear(); //벡터를 초기화해준다.
		}
		count = 0;
		memset(visit, 0, sizeof(visit)); //테스트케이스를 여러 번 돌려야하므로 visit 을 초기화
	}
	return 0;
}

 

참고자료 : memset함수

dbstndi6316.tistory.com/28

[개념정리] memset함수

참고자료 : vector container

dbstndi6316.tistory.com/25

[개념정리] vector container