[백준 / Java] 2668번: 숫자고르기 (골드5)

문제 풀이 날짜: 2023.09.25
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2668번: 숫자고르기 (골드5)

 

키워드

그래프, 사이클 찾기

 

풀이 접근법

• 같은 집합을 형성함 → 주어진 정보를 그래프로 나타낸다면 사이클을 형성한다.
• 따라서 사이클을 형성하는 노드의 번호들과 개수를 찾는다.
  • 이 문제는 한 노드 당 연결된 정점이 단 한개만 존재한다. (1:1 관계)
  • 그렇기 때문에 그래프를 연결리스트가 아니라 아니라 배열로 정의해도 되며, 이 편이 훨씬 풀이가 간단하다.
• 시작점부터 방문 체크를 하고 DFS를 들어가는데...
  • 이 때, 방문했던 점을 다시 방문했다면 && 해당 정점이 시작정점과 동일하다면 사이클을 형성하는 것이다.
  • 해당 정점을 결과 리스트에 넣어준다. 한 번 DFS를 끝냈다면 다른 사이클을 찾을 수 있도록 visited를 원복시켜준다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

	private static int N;
	private static int[] graph;

	private static boolean[] visited;

	private static List<Integer> result = new ArrayList<>();

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

		N = Integer.parseInt(br.readLine());

		graph = new int[N + 1];
		visited = new boolean[N + 1];

		int target = 0;
		for (int i = 1; i <= N; i++) {
			target = Integer.parseInt(br.readLine());
			graph[i] = target; //한 노드에 다른 하나의 노드만 대응 => 배열로 정의 가능
		}

		for (int u = 1; u <= N; u++) {
			visited[u] = true; //시작점
			findCycle(u, u);
			visited[u] = false;
		}

		Collections.sort(result);
		StringBuilder sb = new StringBuilder();
		for (int n : result) {
			sb.append(n).append("\n");
		}

		System.out.println(result.size());
		System.out.println(sb.toString());
	}

	private static void findCycle(int start, int curr) {
		if(!visited[graph[curr]]) {
			visited[graph[curr]] = true;
			findCycle(start, graph[curr]);
			visited[graph[curr]] = false;
		}
		if(start == graph[curr]) { //시작점으로 다시 되돌아왔다면
			result.add(start); //사이클 발생 => 결과 리스트에 추가
		}
	}
}

---

 

 

참고한 링크

https://moonsbeen.tistory.com/176