[백준 10451번/JAVA] 순열 사이클 (문제 풀이, 코드)

순열 사이클

[문제]

[풀이]

첫 번째 인덱스가 가리키는 곳으로 쭉 쭉 쭉 쭉 따라가본다.

사이클이라면, 마지막 점이 다시 첫 번째 인덱스의 점을 가리킨다는 점을 이용하여 DFS로 이 문제를 풀어보자!

 

[내 코드 알고리즘]

방문을 체크하는 visited 배열과, 사이클인지 아닌지를 체크하는 isCycle 배열을 만든다.

첫번째 index가 사이클이 아니라면 탐색을 해봐야하는 경우이므로, DFS 탐색에 들어간다.내가 다음으로 가려는 점이 true면 Cycle이므로 true를 반환.아니면 다음점을 DFS 탐색하여 true면 true를 반환한다.사이클이라면 visited를 초기화시켜주고, isCycle에 사이클에 해당하는 index 모두를 true 체크해준다.

 

[코드]

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

public class Main {
	static int[] P;
	public static void main(String args[])throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			int N = Integer.parseInt(br.readLine());
			P = new int[N+1];
			boolean[] visited = new boolean[N+1];
			boolean[] isCycle = new boolean[N+1];
			st = new StringTokenizer(br.readLine()," ");
			for(int j=1;j<=N;j++) P[j]=Integer.parseInt(st.nextToken());
			int ans=0;
			/* 순열을 찾아볼까 */
			for(int k=1;k<=N;k++) {
				if(!isCycle[k])
					if(DFS(k,visited)) {
						ans++;
						for(int x=1; x<=N; x++)
							if(visited[x]) {
								isCycle[x] = true;
								visited[x] = false;
							}
					}
			}
			System.out.println(ans);
		}
	}
	public static boolean DFS(int k, boolean[] visited) {
		visited[k] = true;
		if(visited[P[k]] == true) return true;
		if(DFS(P[k], visited)) return true;
		return false;
	}
}

[더 효율적인 코드 & 알고리즘]

일단 문제를 맞추긴 했지만, 시간과 메모리가 많이 소모된다.

그리고 코드를 작성하면서도 내 코드가 비효율적이라고 생각이 들었다.더 효율적으로 하려면 어떻게 해야할까?

 

이 gif를 참고하자

 

조금만 고치면 된다!

내가 다음으로 방문하려는 점이, 이미 방문했던 점일 때. 방문했던 점과 제일 처음 dfs로 들어갔던 점이 같다면
Cycle이다!

for문을 돌 때 isCycle대신 visited만 체크하여서 false일 때만 돌게한다.

요론식으로 코드를 짜면 효율적일 것 같다.

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

github.com/MOBUMIN/BJalgorithm/blob/master/10000-10999/PermutationCycle_10451.java

MOBUMIN/BJalgorithm