1. 인접행렬과 인접리스트

참조시 인접행렬이 인접리스트에 비해서 더 빠름( 행렬의 경우 인덱싱으로 바로 접근 가능! 인접리스트의 경우 어쩔수 없이 다음 위치 찾아야 함!)

하지만 공간복잡도가 인접행렬이 더 큼.

대체로 인접리스트로 접근 하는 것이 유리!!(인접행렬로 주면 그대로 가자 )

---

2. Map을 주는 경우

그냥 Map 그대로 이용.
단 시작점을 잘 확인해 주어야 한다.(원점을 (1,1)로 두는 경우가 많음)

---

3. DFS

DFS는 그래프를 탐색할 때 쓰는 알고리즘이며 어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘

pseudocode

DFS(u, adj)
	u.visitied = true
    for each v in adj[u]
    	if v.visited == false
        	DFS(v, adj)

구현방법 1: 돌다리도 두들겨보고 건너기

해당 노드로 가기 전에 방문한 곳인지 확인

구현방법 2: 못먹어도 GO!

일단 가서 이미 방분한 곳이면 return

주요 유형 : floodfill

연결되어 있는 컴포넌트들을 번호를 붙여가며 색칠하는 문제 유형

---

4. BFS

BFS는 그래프를 탐색하는 알고리즘이며 어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다. 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰임

BFS(G, u)
	u.visited = true;
    q.push(u)
    while(q.size())
    	u = q.front()
        q.pop()
        for each v in G.adj[u]
        	if v.visited == false
            	v.visited = true // v.visited ++ 도 가능 
                q.push(v)