DFS/BFS_Python

그래프 탐색 알고리즘

 

 

그래프의 기본 구조

 

1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현

graph_matrix = [[0,7,5],
         [7,0,INF],
         [5,INF,0]]

print(graph_matrix)

 

2. 입접 리스트: 리스트로 그래프의 연결 관계를 표현

graph_list = [[] for _ in range(3)]
# 노드에 연결된 노드 정보 ( 노드, 거리 )
graph_list[0].append((1, 7))
graph_list[0].append((2, 5))
graph_list[1].append((0, 7))
graph_list[2].append((0, 5))

print(graph_list)

 

 

1. DFS

 

- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색

- 스택 자료 구조를 사용

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end='')
    # 현재 노트와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

 

2. BFS

- 너비 우선 탐색

- 가까운 노드부터 탐색

- 선입선출 큐 방식 사용

- 코테에서는 DFS보다 BFS가 (약간 더) 빠르게 작동한다. 

from collections import deque


def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

 

 

---

~ 문제 풀이 ~

 

1. 음료수 얼려먹기

그래프에서 0으로 연결된 개수 세기!

 

1.1 DFS 로 풀어보기

# 1. dfs로 풀어보기
n, m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input())))


# 연결된 노드를 모두 방문으로 바꿔주는 dfs 함수
def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    if graph[x][y] == 0:
        graph[x][y] = 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False

result = 0
for x in range(n):
    for y in range(m):
        if dfs(x,y) == True:
            result += 1

print(result)