[DFS] 인접리스트

들어가면서

그래프 문제를 해결할 때 인접리스트를 사용하게 되는 경우가 잦다.
그런데 나는 인접리스트의 개념을 명확하게 알고있을까?
그래서, 따로 정리해보기로 했다.

인접리스트란?

각 노드마다 연결된 노드들을 리스트로 저장하는 방식이다.

쉽게 말해서 간선에 대한 정보만 저장하는 방식이다.

이해하기 쉽도록 인접리스트를 초기화하는 방식을 코드로 작성해보겠다.

인접리스트 초기화 및 사용 예시

// 인접리스트 초기화
ArrayList<ArrayList<Integer>> graph ;
graph = new ArrayList<ArrayList<Integer>>;

for(int i = 0; i<=n; i++){
	graph.add(new ArrayList<Integer>);
}

// 간선 정보 추가
for(int i = 0; i < m; i++){
	int a = in.nextInt();
    int b = in.nextInt();
    graph.get(a).add(b);
}


// DFS 사용 예시

```java
public void DFS(int v){
	if(v==n) answer++;
    else{
    	for(int nv : graph.get(v)){
        	if(ch[nv]==0){
            	ch[nv] = 1;
                DFS(nv);
                ch[nv]=0;
            }
        }
    }
}

알게된 점

인접리스트와 인접행렬의 차이

인접리스트는 무엇이고, 인접행렬은 무엇일까?

명확하지 않게 기억하고 있는 두 개념을 명확하게 이해해보고 어떠한 사용예시가 있는지, 어떠한 상황에 사용될 수 있는지 알게되었다.

그래프

그래프의 종류를 알게되었다.

그래프 문제에서 인접리스트와 인접행렬이 사용될 수 있다는 사실을 알게되었다.