탐색 알고리즘2 (DFS, BFS)

오늘은 이어서 탐색 알고리즘 DFS, BFS 에 대해 공부하겠다!

사실 차근차근 진도를 나가면서 블로그에 정리하려고 했으나, 항상 밀려서 급하게 정리한다.

알고리즘 개념에 해당하는 간단한 세미코테 문제들도 곧 올리겠다!

 

탐색 알고리즘

: 리스트/배열 내에서 특정 원소를 탐색하는 방법

---

DFS, BFS를 공부하기 전, Stack과 Queue의 자료구조와 그래프에 대해 간단하게 복습하자.

 

자료 구조

• 데이터를 표현 관리 처리하기 위한 구조
• Stack : 선입후출 구조
  • 먼저 들어온 것이 나중에 나간다 
  • first in last out (FILO)
• Queue : 선입선출 구조
  • 들어온 순서대로 나간다
  • first in first out (FIFO)

그래프

• 유한개의 꼭지점 Vertex의 집합 V와 두 꼭지점을 원소로 갖는 변 edge E의 집합
• 표현 방법
  • 인접행렬 
    • 행렬로 표현하는 방식
    • ex. 1번 노드와 2번 노드가 서로 연결되어 있다면,
      1번째 인덱스의 리스트 값을 1 & 2번째 인덱스의 리스트 값을 1로 표현
  • 인접리스트
    • ex. 1번 노드와 2번 노드가 서로 연결되어 있다면,
      1행 2열과 2행 1열의 값을 1로 표현

---

DFS (Depth First Search)

• 그래프 전체를 탐색하는 방법 중 하나
• 트리나 그래프 형태의 데이터 구조를 탐색하기 위한 알고리즘
• 그래프의 깊은 부분을 우선적으로 탐색 (깊이 우선 탐색)
• 방법
  • 경로 설정
  • 막 다른 길이나, 이미 방문한 노드에 도달할 때까지 계속 진행
  • 방문하지 않은 인접 노드가 있는 마지막 노드로 역추적
• 구현
  • g : 인접리스트로 표현된 그래프
  • v : 방문 정보
  • visited : 방문 노드 = 방문 했는지 안했는지 표시 (했으면 True)

graph=[[],[2,4],[1,3],[2,6],[1,5,7],[4,8],[3,9],[4,8],[5,7],[6]]
visited = [False]*10

def dfs_list(graph, v, visited): # 인접리스트
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]: # graph[v] : v와 연결된 노드들의 리스트
        if not visited[i]:
            dfs_list(graph, i, visited)

print("===dfs_list===")
dfs_list(graph,1,visited)

graph2=[[0,0,0,0,0,0,0,0,0,0],[0,0,1,0,1,0,0,0,0,0],
[0,1,0,1,0,0,0,0,0,0],[0,0,1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,1,0,0],
[0,0,1,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,0,0,1],[0,0,0,0,1,0,0,0,1,0],
[0,0,0,0,0,1,0,1,0,0],[0,0,0,0,0,0,1,0,0,0]]
visited2 = [False]*10

def dfs_mat(graph,v,visited): # 인접행렬
    if visited[v]==True:
        return
    else:
        visited[v]=True
        print(v,end=' ')
    for i in range(0, len(graph[v])):
        if graph[v][i]==1:
            dfs_mat(graph,i,visited)

print("")
print("===dfs_mat===")
dfs_mat(graph2,1,visited2)

 

for i in graph[v]: 이 부분을 보면, graph[v] : v와 연결된 노드들의 리스트이고

i가 graph[v]까지 반복한다는 의미는 v와 연결된 노드를 꺼내서 i에 할당하며 반복한다는 의미입니다.

 

---

BFS (Breadth First Search)

• 너비 우선 탐색
• 최단거리
• 가까운 노드부터 탐색하는 알고리즘
• 방법
  • 같은 “레벨”씩 이동하면서 그래프 탐색
• 구현
  • g : 인접리스트로 표현된 그래프
  • v : 방문 정보
  • visited : 방문 노드 = 방문 했는지 안했는지 표시 (했으면 True)

graph=[[],[2,4],[1,3],[2,6],[1,5,7],[4,8],[3,9],[4,8],[5,7],[6]]
visited = [False]*10

def bfs_list(graph,v,visited):
    q =[]
    q.append(v)
    visited[v] = True
    while len(q)!=0:
        n=q.pop(0) # 큐 사용해서 FIFO 방식으로 pop
        print(n, end='')
        for i in graph[n]: # n노드와 연결된 노드들을 i에 할당
            if not visited[i]:
                q.append(i)
                visited[i]=True

def bfs_mat(graph, v ,visited):
    q=[]
    q.append(v)
    visited[v]=True
    while len(q)!=0:
        n = q.pop(0)
        print(n, end=' ')
        for i in range(0, len(graph[n])):
            if graph[n][i] == 1 and visited[i]==False:
                q.append(i)
                visited[i]=True
print("")
print("===bfs_mat===")
dfs_mat(graph2,1,visited2)

 

---

Review

#1 그래프에 경로 있는지 찾는 함수 만들기

: Input = 그래프, 시작점, 끝점 && Output = 경로 있으면 1 없으면 0

• dfs를 변형해서, 찾으면 바로 출력하도록
  • dfs를 그대로 가져다 쓰는 것보다 빠름!

g3_list = [[1,2,3],[0,3],[0],[0,1],[5],[4]]

def is_has_path(g, start, end, path=None):
    if path is None:
        path = []
    path.append(start)
    print(path)
    if start == end:
        return 1
    for i in g[start]:
        if i not in path:
            if is_has_path(g,i,end,path):
                return 1
    return 0

print(is_has_path(g3_list,1,2))

경로가 있는 지 확인하는 것 이므로 깊이 우선 탐색 DFS 사용

1. path가 None인 경우, 빈 리스트로 초기화됨.
2. 시작 노드를 path에 추가하고, 시작점과 끝점이 같으면 경로를 찾은 것이므로 1을 반환함.
3. 시작 노드와 연결된 다른 노드들을 확인하면서, 이미 path에 있는 노드가 아니라면 해당 노드로 이동하여 재귀적으로 is_has_path 함수 호출.
4. 이 과정을 통해 끝점까지의 경로를 찾으면 1을 반환하고, 없으면 0을 반환함.

 

#2 Permutation에서 cycle의 개수 찾는 함수

L = [3,2,7,8,1,4,5,6]

def is_cycle(L, start, visited):
    visited[start] = 1
    n = L[start]
    if visited[n] == 0:
        is_cycle(L, n, visited)

def cnt_cycle(L):
    tmp = [0]
    tmp = tmp+L
    visited = [0]*(len(tmp))
    ret = 0
    for i in range(1, len(tmp)):
        if visited[i] == 0:
            # cycle 측정 
            is_cycle(tmp,i,visited)
            ret = ret+1
    return ret

print("number of cycle?")
print(cnt_cycle(L))