[자바]백준 10451번 순열 사이클. 2021-06-11

 

우선 순열이란 단어를 보자마자, 아 백트레킹을 이용한 순열을 구하는 것인가? 라는 생각이 들었다. 그러나 문제를 계속 읽으니, 그냥 각 인덱스값, 1부터 N까지에 대응되는 값을 이용하여, 인접리스트나 인접행렬을 통해 노드와 노드사이의 관계를 표현한 다음, 연결요소의 개수를 구하면 된다는 것을 알게 되었다.

처음 난, 이전에 풀어봤던 아파트 단지문제나 배추심기 문제 등에서 좌표평면에 (x,y) 좌표로 노드간의 연결관계를 표현 한 것을, 상화좌우 인접한 좌표로 dfs를 통해 끝까지 탐색하며1을 0으로 바꾸고, 그 곳들을 for문을 통해 처음부터 하나하나씩 dfs로 돌릴때, 해당 좌표가 1이면 카운트 해주는 식으로 풀이를 하면 될줄 알았다.

하지만 이 문제는, 좌표로 나타내었을때, 각 좌표들간의 상관관계가 존재하지 않기에 통하지 않는 방법이란 것을 알게 되었다. 그 전 문제들에서 통용되었던 이유는, 좌표의 시각적인 가까움과 인접성(예를들면, 대각선이나 상하좌우옆에 있을시)이 dfs를 하는 기준이 될 뿐이라 그랬던 것 같다. 무엇보다도 그 전 문제들에서는, (x,y) 좌표가 x라는 노드와 y라는 노드가 이어져있음을 표현하는것이 아니라, 단순히, 좌표평면 위에 시각적인 효과를 주기 위한 것이다.

 

하지만 이 문제는, 각(x,y) 대응 관계가 가 실질적인 연결관계를 표현한다는 점에서 난 기존 방법으로 풀면 안된다는생각을 하였다.

 

내가 생각한 풀이법은 우선 기존 dfs 문제들에서는 static 필드에 방문노드를 저장하는 boolean 배열을 공유했다면, 난 각 테스트 케이스마다 새로운 boolean 배열을 생성한 다음, dfs를 돌릴때, 각 boolean배열이 만약, false(방문하지 않은 노드)라면 연결요소 카운트 값인 sum을 하나 올려주는 식으로, 작성하였다. 이유는 배추심기 문제와 마찬가지로, dfs를 한번이라도 돌려버리면, 한 시작노드와 연결된 모든 노드의 boolean값이 true가 되기 때문에, 맨 처음 노드의 boolean 값만 판별해주어도, 연결요소의 개수를 전부 카운트 가능하다. 그런데 어찌됬든, 이 과정은 배추심기 아파트단지 문제들과 풀이원리는 조금 비슷한거 같다.

import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
      int T=s.nextInt();
      for(int t=0;t<T;t++){
          int N=s.nextInt();
          int sum=0;
          boolean[] value=new boolean[N+1];
          ArrayList<Integer>[] arr=new ArrayList[N+1];
          for(int a=0;a<=N;a++){
              arr[a]=new ArrayList<>();
          }
          for(int i=1;i<=N;i++){
              arr[i].add(s.nextInt());
          }
          for(int j=1;j<=N;j++) {
              if(!value[j]) {
                  dfs(j, value, arr);
                  sum++;
              }
          }
          System.out.println(sum);

      }
    }
    static void dfs(int n,boolean[] value, ArrayList<Integer>[] arr){
        if(!value[n]){
            value[n]=true;
            for(int i=0;i<arr[n].size();i++){
                int now=arr[n].get(i);
                if(!arr[now].isEmpty()){
                    dfs(now,value,arr);
                }
                return;
            }
        }
    }
}