그래프 탐색 - DFS (깊이 우선 탐색)

개념

• 그래프를 탐색하는 방법중 하나
• 그래프에서는 탐색을 시작하는 노드를 시작으로 인접한 노트로 지속적으로 이동한다.
• 더 이상 탐색을 하지 않은 인접한 노드가 없을 때 까지 탐색을 진행 후, 부모 노드로 돌아와서 탐색하지 않은 인접한 노드를 탐색한다.
• 인접한 모든 노드가 탐색이 완료되면 종료한다.
• (탐색은 한 번 방문한 노드는 다시 방문하지 않는다.

특징

• 모든 노드를 탐색해야 할 때 활용하기 좋은 방식이다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)에 비해 구현이 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
• 완전탐색 및 백트레킹에 많이 쓰인다.
• 깊이 탐색을 할 때 인접한 노두증에 탐색 순서의 기준도 중요함
• 특정 조건의 여부에 따라 탐색을 중단하는 것에 유용함.

상세

• V: 정점(노드)의 개수
• E: 간선의 개수
• 인접리스트로 표현된 자료구조로 탐색시 시간 복잡도 O(V+E)
• 인접행렬로 표현된 자료구조로 탐색시 시간 복잡도 O(V^2) (인접 행렬은 시간 복잡도가 크기 때문에 인접 리스트로 바꾸어 탐색한다)

DFS(재귀)

• baekjoon 2606 바이러스문제

# baekjoon 2606 바이러스 (DFS, BFS)
# 네트워크를 통해 전파 네트워크 모델 = 그래프
# 컴퓨터의 수와 네크워크 상에서 서로 연결되어 있는 정보가 주어질 때
# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

n = int(input())
e = int(input())
visited: [int] = [0 for i in range(n+1)]
ret = 0
# arr: [[int]] = [[]] * 8
arr = [[] for i in range(n+1)]

for i in range(e):
    n1,n2 = map(int, input().split())
    arr[n1].append(n2)
    arr[n2].append(n1)

def dfs(s: int):

    global ret

    # 방문했다면 continue
    if visited[s] == 1: return

    # 방문 처리
    visited[s] = 1

    ret += 1

    for i in arr[s]:
        dfs(i)


dfs(1)
print(ret - 1)

DFS(재귀 <2차원 맵 형태>)

• 맵의 특정 위치는 y(row) * x(col) 좌표로 나타낸다.
• 아래 코드는 맵을 탐색하면서 connected component를 방문한다.
• n * n의 정사각의 맵이 주어졌다면,
• V = n*n
• E = (n-1)(2n)개
• 시간 복잡도: O(n^2 + 2n^2 - 2n) -> O(n^2)

# baekjoon 2667 단지 번호 붙이기
# 맵 형태의 그래프 문제
# 5 <= N <= 25 의 크기로 완전탐색이 가능한 문제이다.
# Connected Component의 갯수를 출력하고
# Connected Component안의 노드의 갯수를 각각 출력할 것

n = int(input())
arr = []
visited = [[0 for j in range(n)] for i in range(n)]
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
component_cnt = 0
node_cnt = 0
house_count: [int] = []

for _ in range(n):
    arr.append(list(map(int,input())))

def dfs(y: int, x: int):
    global node_cnt
    # 방문처리
    visited[y][x] = 1
    # 단지 내 집 갯수 추가
    node_cnt += 1

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        # OverFlow Check(맵 밖으로 나갔는지 체크)
        if ny < 0 or nx >= n or nx < 0 or ny >= n:
            continue

        # 방문 체크
        if visited[ny][nx] == 1:
            continue

        # 단지가 없으면
        if arr[ny][nx] == 0:
            continue

        # 탐색 제개
        dfs(ny, nx)


for i in range(n):
    for j in range(n):
        # 방문하지 않고
        if visited[i][j] == 0 and arr[i][j] == 1:
            dfs(i, j)
            component_cnt += 1
            house_count.append(node_cnt)
            node_cnt = 0

print(component_cnt)
house_count.sort()

for i in range(len(house_count)):
    print(house_count[i])