09/30 알고리즘

작년에 자바로 공부할떄도 DFS/BFS 여기서 힘들었던 기억이 난다. 특히 인접리스트랑 인접행렬이 그게 그거같은데 왜케 어려운건지...

그리고 행렬은 가로가 행이고 세로가 행인건지... 할때마다 헷갈린다... ㅠㅠ
아래로 내려가는게 행 가로로 가는게 렬

인접리스트 구현 예제를 보면

#행이 3개인 2차원 리스트로 인접 리스트 구현
#[[],[],[]]
graph = [[] for _ in range(3)]

#Node0에 연결된 노드 정보(노드, 거리)
graph[0].append((7,6))
graph[0].append((3,5))

특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.DFS는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 돌아가 따른 경로로 탐색하는 ㅇ라고리즘이다.

1) 탐색 시작 노드를 스택에 삽입하고 방문을 했다고 하자.
2) 스택의 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드를 스택에 넣고 방문을 했다고 한다. 방문하지 않은 노드가 더 이상 존재하지 않는다면 스택에서 맨 위(최상단) 노드를 꺼낸다.
3) 이걸 반복하면서 더 이상 할 게 없으면 종료.

여기서 방문은 스택에 한 번 삽입이 되어서 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 각 노드를 한번씩만 처리.

#DFS 메서드 정의
def dfs(graph, v, visited):
	#지금 현재 있는 노드를 방문 처리
    visited[v] = True #True는 방문 ,False는 방문을 아직 하지 않음.
    print(v)
    for i in graph[v]:
    	if not visited[i]:
        dfs(graph,i,visited)
 
graph = [ []. [2,5,8]........]
visited = [False] * 9
dfs(graph,1,visited)