백준1325 인접행렬과 인접 리스트 차이

이번에 백준 1325번 문제를 풀고  인접 행렬과, 인접 리스트의 차이에 대해 공부를 했다.

 

인접 행렬은 2차원배열로 dfs 그래프를 구현한 것이다.

그래서 장점으로는 구현이 쉽고, 노드끼리 연결이 되어있는지 아닌지 O(1)로 쉽게 알 수 있다. fc [i][j]에서 0인지 1인지만 구분하면 되기 때문이다. 

단점은 노드 i에 연결되있는 노드들을 확인하기 위해서는 fc [i][0] ~ fc [i][V]까지 전체 노드를 방문해야 하기 때문에 O(V)만큼 걸리기 때문이다.

만약에 노드가 수천만개이고, 간선이 달랑 3,4개라고 생각해보면 노드들이 어떻게 연결되어있는지 알아보기 위해서는 O(V^2)만큼 걸리는데, 간선이 노드에 비해 매우 적기 때문에 손해이다. 그래서 이러한 단점을 커버 치기 위해 인접 리스트가 존재한다.

 

인접 리스트는 ArrayList<E>를 사용하여 dfs그래프를 구현한 것이다.

이 문제를 풀면서 ArrayList<ArrayList<Integer>> 대신에 ArrayList<Integer> [] fc; 로 많이들 쓰셨는데 왜 그런지 모르겠다. 왜 그러는지는 나중에 다시 공부해서 알아봐야겠다.

 

그래서 인접리스트로 구현하면 실제로 연결된 노드들에만 정보를 저장한다. 그 말은 만약, 총 6개의 노드 중에 1번 노드에 2 3 4가 연결되어있으면 1 -> 2 3 4 이렇게 저장이 된다. ArrayList는 동적 배열이기 때문에 개수만큼 저장이 된다. 그래서 인접 행렬의 단점인 간선이 노드에 비해 적을 때, 한 노드의 원소의 개수합이 간선의 개수와 같기 때문에 O(E)의 시간이 걸리게 된다. 

 

하지만 단점은 노드i 와 j가 연결이 되어있는지 확인할 때는, 인접 행렬은 O(1)이었지만, 인접 리스트는 fc [i]의 ArrayList를 전부 돌면서 j 성분이 있는지 없는지 확인해야 하기 때문에, O(V)의 시간이 걸리게 된다. 

 

따라서 문제를 보면서 시간복잡도의 비교에 따라, 인접 행렬을 사용해도 되는지, 인접 리스트를 사용해도 되는지의 여부 판단을 잘해야 할 것 같다.