[알고리즘 PS] 백준 10451번 순열 사이클 자바 문제풀이

문제

해당 포스팅은 백준의 10451번 순열 사이클 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이번 문제는 지난번 풀었던 연결 요소의 개수문제와 매우 유사한 문제이다.

 

문제가 이야기하고 있는 것은 이렇다.

 

순열의 길이가 먼저 주어진다.

그리고 그 길이만큼 순열이 들어오는데, 그 순열은 1 ~ N 까지 순서대로 나열한 순열의 인덱스와 1:1 매칭되어 해당 매칭 자첵가 그래프 노드의 연결 상태라고 한다.

문제의 특성상 수열로 만든 그래프는 무조건 사이클을 갖게 된다.

 

그럼 지난번 풀었던 연결 요소의 개수문제와 동일한 문제가 되는 것이다.

오답 후보

이 문제는 방향이 있는 방향 그래프이다.

 

인접 리스트를 구현할 때 양방향이 아니기 때문에 graph.add를 한 번만 수행하면 된다.

양방향(무방향) 그래프 요소 추가.

for (int i = 1; i <= n; i++) {
  graph.get(n1).add(n2);
  graph.get(n2).add(n1);
}

단방향(방향) 그래프 요소 추가.

for (int i = 1; i <= n; i++) {
  graph.get(n1).add(n2);
}

정답 코드

public class Main {

    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            visited = new boolean[n + 1];
            graph = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }

            String[] seq = br.readLine().split(" ");

            for (int i = 1; i <= n; i++) {
                int number = Integer.parseInt(seq[i-1]);
                graph.get(i).add(number);
            }
            int answer = 0;
            for (int i = 1; i <= n; i++) {
                if(dfs(i)) answer++;
            }
            bw.write(answer + "\n");
            bw.flush();
        }
        bw.close();
    }

    private static boolean dfs(int x) {
        if(visited[x]) return false;
        visited[x] = true;
        for(int value: graph.get(x)) {
            if (!visited[value]) dfs(value);
        }
        return true;
    }
}

---

문제 회고

이번 문제는 지난 DFS와 BFS처럼 출력 처리를 제대로 하지 않아서 2번이나 틀렸던 문제이다.
저번에 분명 출력 처리 잘 하자고 다짐 했는데,, 멍청인가보다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.