백준 No.10451 순열 사이클 - JAVA

문제

 

 

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

10451번: 순열 사이클

 

이 부분이 잘 이해가 안 갔는데 이 부분을 코드로 보면 

사이클을 이런식으로 만들 수 있다. 이렇게 만들어진 사이클을 구해 출력하는데 여기서 테스트 케이스 숫자도 주어진다.

 

1. arr을 만들어 주어진 숫자를 배열에 넣는다.

2. visited 배열을 만들어 방문처리를 하는데(여기서 visited 인덱스가 그래프를 나타냄 1~i) 

3. 만약 방문하지 않은 곳이면 방문 처리 후 해당 그래프가 가리키는 그래프가 방문처리 되어있는지 체크하고 안 되어있으면 타고 들어간다. (arr[visited인덱스])  ==>

   visited[for 루프에서 돌고 있는 i] = true;  

   int next = arr[for 루프에서 돌고 있는 i];  ==> 1(i) 가 가리키는 곳은 3(주어진 그래프) 이므로 next는 3

   이러고 끝나는게 아닌 3이 가리키는 곳도 조회하고 계속해서 조회하는데 만약 조회하는 도중 방문처리가 된 곳이

  있을 경우 사이클이 있는 것이므로 찾은 것이다.

  while(true){    //방문한 곳을 찾을때까지

    if(visited[next]){

           count++;

           break;

   }

    visited[next] = true;

    next = arr[next];

}

 

 

 모든 그래프는 1부터 시작이라고 보면 편하다 for문은 기본 0에서 배열 크기만큼 돌지만 1부터 시작할 경우 배열 크기를 포함하고 기존 배열 크기를 +1하는 식으로 진행한다면 visited 같은 배열의 인덱스를 그래프 자체로 사용할 수 있다.

package com.example.algorithgm.BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T ; i++){
            int count = 0;
            int N = Integer.parseInt(br.readLine());
            int arr[] = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j =1;j<arr.length;j++){
                    arr[j] = Integer.parseInt(st.nextToken());
            }
            boolean visited[] = new boolean[N+1];

            for(int a=1;a<=N;a++){

                if(!visited[a]){
                    visited[a] = true;
                    int next = arr[a];

                    while(true){
                        if(visited[next]){
                            count++;
                            break;
                        }
                        visited[next] = true;
                        next = arr[next];
                    }
                }
            }

            System.out.println(count);
        }

    }
}