[1028알고리즘 FROM 동빈나 21]그래프 탐색 : DFS vs BFS

DFS

Depth-first search : 깊이 우선탐색 - 스택(선입후출, 바구니, append, pop), 재귀함수로 구현 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.  2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있으면    << 방문기준 문제마다 임의. 작은걸로 임의 정함 그 노드를 스택에 넣고 방문 처리합니다.  방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다.  3. 더이상 2번의 과정을 수행할수 없을 때까지 반복 그외 - Backtracking : 꼬리잡기 : 한노드의 처음부터 끝까지 탐색하는 과정, 비효율적 어려울때 쓰는 최후의 보루.  - 트리 운행법    inorder  : 좌측 가운데 우측    preorder : 가운데 좌측 우측    postorder : 좌측 우측 가운데

BFS

breadth-first search :너비 우선탐색 -  큐(선입선출, 터널, append, popleft - from collections import deque 라이브러리 임포트)로 구현 - 인접노드 방문, 주로 최단거리 문제 - 모든 노드 방문안해도 됨.  1. 탐색 시작 노드를 큐에 삽입하고 방문처리 2. 큐에서 노드를 꺼낸뒤 해당 노드의 인접노드 중에서 방문하지 않는 노드를 모두 큐에 샆입 방문처리 3. 더이상 2번과정 수행없을 때까지 반복

자바: https://www.youtube.com/watch?v=_hxFgg7TLZQ

주로참고 >>>>>>>>>파이썬 : https://youtu.be/7C9RgOcvkvo   

 

 

 

graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]  ] visited = [False] *9 dfs(graph, 1, visited) bfs(graph, 1, visited)
GFS	BFS
1>2>3 넣었다 꺼냄 > 1>2 1>4>5 넣었따 꺼냄 1>4>6 ... from __future__ import division def dfs(graph, v, visited):     visited[v] = True     print(v,  end=' ')     for i in graph[v]:         #print("-- " + str(i))         #print(visited)         if not visited[i]:             dfs(graph, i, visited)	1 넣었다 꺼냄 1 |2 - 3 - 8 1 2 | 3 - 8 - 7 1 2 3 | 8 - 7 -4- 5 ..: 간선동일 최단거리 쉬움.  from __future__ import division from collections import deque def bfs(graph, start, visited):     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 bfs(graph, 1, visited)

 

* breadth :폭, 너비, 브레드  =width   ex) He was surprised at her breadth of reading

* adjacent: 인접한 어제이센트

* queue : 큐 대기행렬, 줄

 

 

파이썬

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

print(stack)  # 최 하단 원소 부터 출력

print(queue) # 먼저 들어온 원소 부터

queue.reverse()

print(queue) # 나중에 들어온 원소 부터

 

 

추가문제 1. 

# N x M 얼음틀.
# 구멍뚫려 있는 부분 0, 칸마기 1
# 상, 하, 좌, 우 붙어있는경우 서로 붙어있는것으로 간주.
# 생성되는 아이스크림갯수는?
# 1<=N, M<-1000
print("입력하세요")
#5 4
#00110
#00011
#11111
#
00000

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

print(graph)
graph.pop()
print(graph)

def dfs_ice(x,y):
    if x <= -1 or x >= n -1 or y <= -1 or y >= m-1:
        return False
    elif graph[x][y] == 0:
        graph[x][y] = 1
        dfs_ice(x-1, y)
        dfs_ice(x, y-1)
        dfs_ice(x+1,y)
        dfs_ice(x,y+1)
        return True
    return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs_ice(i, j):
            result +=1
print(result)

 

# 미로탈출 최소 칸이 갯수
#
"""
5 6
101010
111111
000001
111111
111111

10
"""

from collections import deque

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

print(graph)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1,1]

def bfs_miro(x,y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x,y = queue.popleft()
        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
            elif graph[nx][ny]==0:
                continue
            elif graph[nx][ny] ==1:
                graph[nx][ny]= graph[x][y] +1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs_miro(0,0))

 

> 자바 버전 참고: https://blog.1028web.com/entry/class