8주차 스터디 그래프 이론 - 백준 10451번 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

IDEA

여러가지 방법이 있을 수 있겠다. 

뭐 유니온파인드를 쓰는 방법도 있겠지만,,,, 

arr라는 배열에 저장한 후, 배열값을 인덱스로 가지는 그 다음 배열로 넘어가면 될 거 같다. 

사이클인지 아닌지 구분하는 방법은 이미 지나온 곳으로 다시 돌아간다면 사이클이다.

1	2	3	4	5	6	7	8
3	2	7	8	1	4	5	6

1부터 시작해서 arr[1]이 가르키는 3을 인덱스로 하는 곳으로 넘어간다. 

arr[3]이 가르키는 7을 인덱스로 하는 곳으로 넘어간다.

arr[7]이 가르키는 5를 인덱스로 하는 곳으로 넘어간다. 

arr[5]가 가르키는 1은 이미 한 번 지나왔던 곳이다. 

즉 사이클이 1 - 3 - 7 - 5 이렇게 생기는 것이다. 

 

사이클이 생겨 반복문이 끝났다면 그 다음 2로 넘어간다.

arr[2]가 가르키는 2는 이미 지나온 곳이다. 사이클은 2 하나

 

그 다음 3으로 넘어간다. 

arr[3]은 이미 방문처리가 되어있으니 넘어간다. 

 

1. 방문이 되었다면 그 다음 인덱스로 넘어간다.

2. 방문처리 및 싸이클을 하나 카운팅 한 후 while문을 통해 싸이클을 찾아내자.

3. 만약 현재노드가 이미 방문되었다면 싸이클이 하나 생겼다는 뜻이므로 반복문을 종료한다.

 

CODE C++

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>
#include<string.h>

using namespace std;

int num[1005] = { 0 };
bool visited[1005] = { false };

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc) {
		tc--;
		int n;
		scanf("%d", &n);

		memset(num, 0, sizeof(num));
		memset(visited, false, sizeof(visited));

		for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
		int count = 0;
		for (int i = 1; i <= n; i++) {
			if (visited[i]) continue;
			int temp = num[i];
			visited[i]= true;
			count++;
			while (!visited[temp]) {
				visited[temp] = true;
				temp = num[temp];
			}
		}
		printf("%d\n", count);
	}
}

 

CODE -Python

tc = int(input())
for _ in range(tc) :
  n = int(input())

  arr = [0] + list(map(int,input().split()))
  visited =[False for _ in range(n+1)]

  cycle = 0
  for i in range(1,n+1):    
    if (visited[i]) : continue
    cur_node = i
    cycle += 1
    visited[cur_node] = True
    cur_node = arr[cur_node]
    while True:
      if visited[cur_node] : break
      visited[cur_node] = True
      cur_node = arr[cur_node]
  print(cycle)