[JAVA] ArrayList를 사용하여 그래프의 연결 정보를 저장하기

 

📢 인접 리스트 알아보기 

 

보통 자바에서 그래프를 구현할 때 인접 행렬이나 인접 리스트를 통해 연결된 노드의 정보를 저장한다. 

 

인접 행렬은 2차원 배열을 이용해 연결을 표현한다.  

인접 리스트는 각 노드에 연결된 노드를 리스트에 저장한다.

 

그래프의 연결 정보를 인접 행렬과 인접 리스트로 어떻게 변환하는지 자세히 알아보자

 

우선 그래프에는 무방향 그래프와 방향 그래프가 있는데 이에 따라 인접 행렬과 인접 리스트의 형태도 달라진다.

 

 

 

 

인접 행렬을 이용하면 연결이 별로 없는 희소그래프를 표현할 때 메모리 낭비가 심하다. 

그래서 나는 주로 인접리스트를 많이 사용한다. 

 

 

 

📢 인접 리스트에 연결 정보 저장하기

 

 

우선 인접리스트로 그래프를 표현하기 위한 방법은 다음과 같다.

(무방향그래프라고 가정하고 설명할게요~:))

 

① 연결 리스트 선언 

② 리스트 초기화

③ 연결 정보 저장

 

 

 

1️⃣ 연결 리스트 선언 

ArrayList를 사용하여 연결 리스트를 선언하는 방법에는 2가지가 있는데 

① 2차원 ArrayList를 생성하는 방식과 ② ArrayList 객체들을 저장할 배열을 생성하는 방식이다. 

 

① 2차원 ArrayList를 생성

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

 

② ArrayList 객체들을 저장할 배열을 생성 (대부분 이거 사용)

ArrayList<Integer>[] adj = new ArrayList[n + 1];

 

첫 번째 방법은 노드의 수가 동적으로 변화할 가능성이 있을 때 사용하고,

두 번째 방법은 배열의 길이는 가변적이지 않기 때문에 노드 수가 고정되어있을 때 사용한다. 

 

 

보~통은 대부분의 알고리즘 문제에서는 노드 수가 입력으로 주어지거나 명확히 정의된다.

그래서 2번째 방법을 많이 사용한다. 

 

 

 

 

 

2️⃣ 리스트 초기화

이렇게 리스트를 선언하면 배열의 값은 null로 초기화되어있기 때문에 모든 배열을 초기화 해주어야한다. 

for (int i = 1; i <= n; i++) {
	adj[i] = new ArrayList<>();
}

 

 

 

 

3️⃣ 연결 정보 저장

1 6
6 3
3 5
4 1
2 4
4 7

보통 문제에서 이렇게 연결된 두 정점을 나열해준다. 

 

for(int i=1; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adj[a].add(b);
            adj[b].add(a);
}

 

이렇게 두 노드에 모두 연결된 노드의 정보를 추가해준다. 

 

그럼 

1 > 6, 4

2 > 4

3 > 6, 5

4 > 2, 7

5 > 3

6 >1,3

7 >4

 

이러한 형태로 저장되게 된다.

 

 

 

📢 마지막으로 기억할 ~ 것 

보통 이렇게 인접리스트를 통해 문제를 해결할 때에는 

방문 체크 배열과 큐를 사용한다. 

 

< 인접리스트, 방문 체크 배열, 큐 > 이 삼총사를 기억할 것!!

 

한 노드에서부터 연결된 노드를 차례차례 이동하는데 방문한 노드는 큐에 넣지 않음으로써 

효율적인 문제 해결을 할 수 있다!

 

        boolean[] visited = new boolean[n + 1]; //방문 체크 배열

        ArrayList<Integer>[] adj = new ArrayList[n + 1]; //연결 리스트
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        Queue<Integer> queue = new LinkedList<>(); //큐

 

삼총사맨~

 

<수정> 

음,,,,, 정확하게 말해서 큐는 bfs로 문제를 해결할 때 사용된다. 

dfs로 그래프 문제를 풀이할 수도 있으니,,, 그때는 재귀를 주로 사용할 것이다. 

 

 

 

그럼 이제 그래프 문제를 와구와구 풀어보자!