동빈나 2021 이코테_3.DFS & BFS

대표적 그래프탐색 알고리즘 : DFS / BFS

 

탐색이란, 많은 양의 데이터중 원하는 데이터를 찾는 과정

 

<스택 구현예제> _ 파이썬에서는 간단히 리스트로 스택 구현 가능

< 큐 구현예제 > 

< DFS>

DFS : 깊이우선 탐색으로 가장 깊은곳까지 먼저 탐색하는 방식

DFS는 스택자료구조(혹은 재귀함수)를 이용한다.

1. 시작노드를 스택에 삽입 / 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다.

< BFS >

너비우선탐색으로 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

BFS는 큐를 이용한다.

1. 탐색 시작노드를 큐에 삽입 & 방문처리

2. 큐에서 노드를 꺼내고, 해당노드의 인접노드중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다.

<예제문제1 _ 음료수 얼려먹기 >

연결요소 _ connected component찾기

 

얼음을 얼릴 수 있는 공간이 상하좌우로 연결되어 있다고 표현할 수 있으므로 그래프형태로 모델링 할 수 있다.

각 위치에서 상하좌우는 인접한 노드로 취급

특정지점에서 DFS, 혹은 BFS를 수행해서 이동가능한 모든 경우에 대해서 방문처리를 하도록 하는것

import sys
input = sys.stdin.readline

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

# x - 4, y - 5

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

# 현재로부터, 상하좌우 가능하면 움직일수 있는데, 움직였을때 0이면 2로 바꾸고(방문처리) 1이면 못움직임
# 그래프 전체를 돌면서 0인부분에서 dfs호출 (포문 두번)

def dfs(x,y,graph):
    graph[x][y] = 2 #방문처리

    for i in range(4):
        if x+dx[i] >= 0 and x+dx[i]<4 and y+dy[i] >=0 and y+dy[i] < 5:
            if graph[x+dx[i]][y+dy[i]] == 0: #움직가능 and 방문가능 (1이면 못움직, 2도 못움직)
                dfs(x+dx[i],y+dy[i], graph)


answer = 0
for i in range(len(graph)): #행
    for j in range(5): #열
        if graph[i][j] == 0:
            dfs(i,j,graph)
            answer+=1

print(answer)

 

 

 

 

 

 

출처 : www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

동빈나