[JAVA] ArrayList 2차원 배열과 정렬

자료구조를 복기하던 중 DFS를 구현하기 위한 방법에 스택과 이중 ArrayList가 있다는 것을 알게되었다.
이 두 방법은 사실상 같은 원리지만 코드상에서는 차이가 존재한다.

실제 코드를 구현할 때는 스택보다 이중 ArrayList를 더 많이 사용한다고 알고있고, 나는 이보다도 ArrayList 2차원 배열 코드를 사용해보았다.

아래 코드는 백준에서 DFS 문제 정답코드의 일부분이다.

public class Main{
  static boolean[] visited;
  static ArrayList<Integer>[] A;

    public static void main(String[] args) throws IOException {
      visited = new boolean[N + 1];
      A = new ArrayList[N + 1];
    }
    
    for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        A[n1].add(n2);
        A[n2].add(n1);
    }

    for (int i = 1; i <= N; i++) {
        Collections.sort(A[i]);
    }
}

방향성이 존재하지 않는 그래프이기 때문에
A[n1].add(n2);
A[n2].add(n1);
위처럼 두 정점의 ArrayList에 서로를 추가하였다.

이후 각 리스트마다의 요소를 오름차순 정렬하기 위해 Colletsions.sort를 사용했는데
이렇게 했을경우 정렬이 된것을 눈으로 확인하고 싶었다.

간선을 (1,4) (1,2) (2,3) (2,4) (3,4) 입력했을 경우

[2, 4] , [1, 3, 4] , [2, 4] , [1, 2, 3] , [ ]

로 잘 정렬이 되어 출력된것을 볼수있었다.

처음에는 첫 번째 for문에서 간선을 입력 받음과 동시에 하나의 간선에 두 개의 정점에 대해
각각 Collection.sort 를 했지만, 아래와 같이 for문을 따로 빼서 각 리스트의 시작점부터만 정렬을 해주면 자연스럽게 오름차순으로 방문할 수 있다는 것을 알 수 있었다.