[Java] BOJ10451 - 순열 사이클

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

10451번: 순열 사이클

 

 

💡 포인트

1️⃣ 각 정점마다 인접한 정점 파악하여 배열에 기록

2️⃣ 사이클 판단 시 이미 지나갔던 정점 즉, 사이클 안에 이미 포함되었다고 판단된 정점 방문처리

3️⃣ 사이클 판단 시 이미 지나갔던 정점에 도달했다면 사이클 개수 +1

 

 

💬 예제 이해하기

예제 입력 1

처음에 문제가 한번에 읽히지 않아 두세번 다시 읽었던 문제라서 간단히 문제를 이해하고 넘어가고자 한다.

첫째 줄에는 테스트 케이스의 개수 T값

둘째 줄부터는 순열의 크기 N의 값 한 줄과 순열의 정보 한 줄씩 테스트 케이스의 개수만큼 번갈아 나온다.

 

내가 헷갈렸던 부분은 순열에 대한 설명이었다.

첫번째 테스트 케이스를 예시로 살펴보자.

다음과 같이 1부터 시작하는 N만큼 크기의 배열이 있다고 가정한다면

첫번째 테스트 케이스의 연결 정점은 다음과 같다

1번 정점 → 3번 정점, 2번 정점 → 2번 정점, 3번 정점 → 7번 정점...

이런 식으로 연결을 짓고 그림을 그려보면 아래와 같이 3개의 사이클이 만들어지는 것을 알 수 있다.

 

 

1️⃣ 2차원 인접행렬을 이용한 첫번째 시도

✨ 코드 효율

👉 메모리 : 309368 KB

👉 시간 : 2464 ms

👉 (주석 제외한)코드 길이 : 1262 B

 

✔ 소스코드

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

public class Main { // 순열 사이클

	static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[][] adj = new int[N + 1][N + 1]; // 인접행렬
			boolean[] visited = new boolean[N + 1];
			cnt = 0;
			
			// 인접행렬 정보 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int spot = Integer.parseInt(st.nextToken());
				adj[i + 1][spot] = 1;
			}

			for (int i = 1; i < adj.length; i++) {
				for (int j = 0; j < adj[i].length; j++) {
					if(!visited[i] && adj[i][j] == 1) {  // 방문하지 않은 정점이고 i에서 j로 인접한 관계라면
						visited[i] = true;
						isCycle(adj, visited, i);
					}
				}
			}
			System.out.println(cnt);
		}
	}
	
	private static void isCycle(int[][] adj, boolean[] visited, int idx) {
		for (int i = 1; i < adj[idx].length; i++) {
			if(adj[idx][i] == 1) { // 인접한 관계라면
				if(visited[i]) {  // 이미 방문했던 정점이라면
					cnt++;  // 사이클 맞음
					return;
				} else {
					visited[i] = true;
					isCycle(adj, visited, i);
				}
			} 
		}
	}
}

엄청 큰 메모리 사용량과 오래 걸리는 시간, 긴 코드 길이...세 가지 모두 마음에 들지 않는 결과였고 어떻게 하면 코드를 조금 더 효율적으로 작성할 수 있을지 고민해보았다.

 

 

2️⃣ 1차원 배열을 이용한 두번째 시도

✨ 코드효율

👉 메모리 : 52208 KB

👉 시간 : 548 ms

👉 (주석 제외한)코드 길이 : 1128 B

 

✔ 소스코드

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

public class Main { // 순열 사이클

	static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[] adj = new int[N + 1]; // 인접정점 표시
			boolean[] visited = new boolean[N + 1];
			cnt = 0;
			
			// 인접행렬 정보 입력
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int spot = Integer.parseInt(st.nextToken());
				adj[i+1] = spot; 
			}

			for (int i = 1; i < adj.length; i++) {
				if(!visited[i] && adj[i] != 0) {  // 방문하지 않은 정점이고 i정점에서 인접한 정점이 있다면
					visited[i] = true;
					isCycle(adj, visited, i);
				}
			}
			
			System.out.println(cnt);
		}
	}
	
	private static void isCycle(int[] adj, boolean[] visited, int idx) {
		if(adj[idx] != 0) {  // 인접한 정점이 있다면
			if(visited[adj[idx]]) {  // 이미 방문했던 정점이라면
				cnt++;  // 사이클 맞음
				return;
			} else {  // 방문하지 않은 정점이라면
				visited[adj[idx]] = true;  // 방문 표시
				isCycle(adj, visited, adj[idx]);  // 다음 정점으로 넘어가서 다시 사이클 유무 판단
			}
		}
	}
}

1차원 배열을 이용하여 문제를 해결함으로써 2중 for문을 단일 for문으로 변경하여 해결하였다.

그 결과, 코드 길이는 크게 차이는 없었다. 그러나 메모리 사용량이 크게 줄었고 시간 또한 4배 넘게 단축된 것을 확인할 수 있었다😀