[백준 10451] 순열 사이클 (자바)

백준 10451번 순열 사이클 (자바)

 

 

 

출처

www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

 

 

문제

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

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

순열을 배열을 이용해

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

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

접근 방법

처음에는 인접행렬을 만들어 계산하려고 했지만 시간 초과... 다시 보니까 조건 범위가 엄청 컸다.

1. 시간복잡도를 위해 인접 리스트를 만든다.

2. 입력 순서대로 인접리스트에 값을 넣는다.

3. 방문 안되어 있는 경우에 탐색을 시작한다.

4. 받아온 행을 방문처리하고, 해당 행에 방문하지 않은 노드가 있으면 탐색한다.

5. 3,4번을 반복한다.

 

 

※ 의문점

입력값을 BufferedReader로 사용했을 때는 런타임 에러가 났지만, Scanner를 사용했을 때는 통과했다. 이유가 무엇일까..

 

-> 해결 (입력받을 때 한줄로 받아야 한다.)

런타임 에러는 실행 중에 에러가 발생했다는 뜻이다.

문제에서 순열을 이루는 정수는 공백으로 구분되어 주어진다고 했으니 35번째 줄(int v = Integer.parseInt(reader.readLine());)과 같이 한 줄에 하나씩 정수가 있다고 가정하고 입력받으면 안 되고,

한 줄만을 받은 뒤 공백을 기준으로 나누어 각각을 정수형으로 바꿔주어야합니다.

Scanner로 바꾸셨을 때 된 것은 nextInt로 공백으로 구분된 수들을 입력받는 데에 문제가 없었기 때문입니다.

 

 

내 코드

package dfsbfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

public class PermutationCycle {
	private static ArrayList<Integer>[] map;
	private static boolean[] visit;
	private static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {

		// 12345678
		// 주어진 순열
		
		Scanner sc = new Scanner(System.in);
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		//int t = Integer.parseInt(reader.readLine());
		int t = sc.nextInt();

		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < t; i++) {
			// t번
			//int n = Integer.parseInt(reader.readLine());
			int n = sc.nextInt();

			//인접리스트
			map = (ArrayList<Integer>[]) new ArrayList[n+1];
			visit = new boolean[n+1];
			cnt = 0;
			
			//초기화
			for (int j=0; j<=n; j++) {
				map[j] = new ArrayList<Integer>();
			}
			
			//값 입력
			for (int j=1; j<=n; j++) {
				//int v = Integer.parseInt(reader.readLine());
				int v = sc.nextInt();
				
				map[j].add(v);
			}
			
			//방문 안되어 있는 리스트 탐색
			for (int j=1; j<=n; j++) {
				if (!visit[j]) {
					dfs(j);
					cnt++;
				}
			}
			sb.append(cnt + "\n");
		}
		
		System.out.print(sb);

	}

	private static void dfs(int start) {
			
		//방문전적 있으면 종료
		if (visit[start]) {
			return;
		}
		
		//방문처리
		visit[start] = true;
		
		//해당 리스트에서 방문한적 없으면 탐색
		for (int i : map[start]) {
			if (!visit[i]) {
				dfs(i);
			}
		}
		
	}
}

 

 

 

고려할 점

1. 인접리스트를 사용할 것

2. 방문처리를 통한 탐색