[アルゴリズム]グラフィックナビゲーションアルゴリズム:DFS/BFS

何が探求ですか?

スタック実装例

stack = []

stack.append(5)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.appned(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

출력 -> 
[1,3,5]
[5,3,1]

キューの実装例

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(1)
queue.append(7)
queue.popleft()

print(queue) # 먼저 들어온 순서대로
queue.reverse() # 역순으로
print(queue) # 나중에 들어온 순서대로

출력 ->
deque([3,1,7])
deque([7,1,3])

再帰関数の例

def recursive_function():
    print('재귀 함수를 호출한다.')
    recursive_function()
    
recursive_function()

終了条件を含む再帰関数の例

def recursive_function(i):
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출한다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료한다.')
    
recursive_function(1)

プラント実装例

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1)
        result *= i
    return result
    
# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:  # 1!은 1이므로 1반환
        return 1
    return n * factorial_recursive(n-1)

再帰関数の例-ユークリッド弧除去法

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

print(gcd(192, 162))

DFS (Depth-First Search)

は、第2のプロセスが実行されなくなるまで繰り返される.

->1-2-7-6-8-3-4-5、ナビゲーション

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

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth-First Search)

を繰り返します.

-> 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

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
                
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
bfs(graph, 1, visited)

n, m = map(int, input().split())
 
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
     
def dfs(x, y):
    # 주어진 범위를 벗어나는 경우 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 방문하지 않았다면
    if grapn[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 i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1
            
print(result)

from collections import deque

n, m = map(int, input().split))
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# 이동할 네 방향 정의 (상하좌우)
dx = [-1, -1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    # 큐가 빌때까지 반복
    while queue:
        x, y = queue.popleft()
        # 현 위치에서부터 4가지 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 공간을 벗어나면 무시
            if nx < 0 or nx > n or ny < 0 or ny > m:
                continue
            # 0 이면 괴물이기때문에 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드 처음 방문시 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]
    
print(bfs(0,0))