dfs와 bfs

(1) 깊이 우선 탐색 DFS

dfs : 깊이우선 탐색으로 넓게 퍼지며 탐색하는 것이 아니라 가장 깊은 곳까지 우선 탐색 후 넓게 퍼져가며 탐색하는 방법.

=> 깊이를 우선으로 먼저 탐색하고 탐색이 끝난 후에는 탐색을 시작한 위치로 돌아와 넓게 퍼지며 또 다른 노드에서 깊은 곳까지 탐색하는 방법.

=> 따라서, 중요한 것은 탐색한 지점을 기억해놔야한다는 점이고 이를 위해 재귀를 적절히 사용할 예정이다.

=> 익숙해지면 반복문을 통한 방법보다 재귀를 사용해 stack을 구현하는 것이 편리.

 

(2) 너비 우선 탐색 BFS

bfs : 너비 우선 탐색으로 넓게 퍼지며 현 위치 노드에 연결된 모든 노드를 우선으로 탐색하고 그 다음으로 한번 깊이를 들어가주며 그 노드의 연결된 모든 노드를 우선으로 탐색하는 방법

=> 한 노드에 연결된 모든 노드를 탐색하고 그 저장된 모든 노드들에 연결된 노드를 또 같은 방법으로 탐색하는 방법

=> bfs는 각 노드에 연결된 모든 노드를 queue에 저장하고 popleft()를 사용하며 먼저 저장한 것을 꺼내어 탐색해야하는 방법이기에 queue를 사용.

 

---

1. dfs와 bfs사용을 위한 스택, 큐, 재귀함수에 대한 기본 예제

#1. 스택 예제

stack =[]

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

print(stack)
#print(stack[::-1]) => 마지막에 넣은 것부터 출력할때 -> ::-1을 사용

#2. 큐 예제 
from collections import deque

queue = deque()

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

print(list(queue))
#queue.reverse() => 역순으로 바꿔서 첫번째 원소부터 출력가능
#print(queue)


#3. 재귀함수 100번 호출하는 예제

def re_func(i):
    if i==100:
        return
    else:
        print(i)
        return re_func(i+1)

re_func(0)

2. dfs와 bfs 개념잡기[+인접행렬, 인접리스트 구현방법]

#1.인접행렬
#인접행렬을 사용한 비용 및 연결성 나타내기
INF = 999999999

graph = [ [0,7.5],[7,0, INF],[5,INF, 0 ]]

print(graph)

#2.인접 리스트를 통한 그래프에 튜플로 (노드번호, 가중치) 넣기 
#만약 노드가 3개면 3개의 행을 사용하고 열은 각 노드에 연결된 노드의 개수가 결정함. => memeory효율적

graph =[[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))
graph[1].append((0,7))
graph[2].append((0,5))

print(graph)

#3. stack과 재귀함수를 활용한 dfs예제풀기
graph = [[],[1,2,3,8],[1,2,7],[1,3,4,5],[3,4,5],[3,4,5],[6,7],[2,6,7,8],[1,7,8]]

stack=[]
visit=[0]*9
def re_func(i):
    i = stack.pop()
    visit[i]=1
    print(i, end='')
    for j in graph[i]:
        if visit[j]!=1 and j!=i:
            stack.append(j)
            re_func(j)

stack.append(1)
visit[0]=1

re_func(1)

#4. bfs 알고리즘 : 너비우선 탐색
from collections import deque

queue= deque()

graph = [[],[1,2,3,8],[1,2,7],[1,3,4,5],[3,4,5],[3,4,5],[6,7],[2,6,7,8],[1,7,8]]
visit=[0]*9
visit[0]=1
visit[1]=1
queue.append(1)

for i in graph[1]:
    if i!=1:
        visit[i]=1
        queue.append(i)

while(1):
    i = queue.popleft()
    print(i,end='')
    for j in graph[i]:
        if j!=i and visit[j]==0:
            queue.append(j)
            visit[j]=1
    
    if len(queue)==0:
        break

---

<기본 문제 풀어보기>

1. 하나의 지점에서 그 지점과 연결된 것들을 그룹화 시키는 문제

2. 하나의 지점에서 출발해 다른 지점으로 도달할때 몇번만에 갈 수 있는지 생각하는 문제

#1. 음료수 얼려 먹기 => 스택으로 들어가서 0이 연결된부분까지 계속 추적 -> 상하좌우로 계속
#얼음틀에 대한 list를 입력받는데 이때 1이 틀이고 0이 가능한 부분.
#최대몇개의 아이스크림이 나올 수 있는가?

n,m = map(int, input().split())

visit=[]
for i in range(0,n):
    list_=[0]*m
    visit.append(list_)

ice =[]
for h in range(0,n):
    list_=list(map(int,input().split()))
    ice.append(list_)


cnt=0
def dfs(i,j):
    
    visit[i][j]=1

    if i-1>=0 and (visit[i-1][j]==0 and ice[i-1][j]==0):
            dfs(i-1,j)
    if i+1<n and (visit[i+1][j]==0 and ice[i+1][j]==0):
            dfs(i+1, j)
    if j-1>=0 and (visit[i][j-1]==0 and ice[i][j-1]==0):
            dfs(i,j-1)
    if j+1<m and (visit[i][j+1]==0 and ice[i][j+1]==0):
            dfs(i,j+1)

for i in range(0,n):
    for j in range(0,m):
        if ice[i][j]==0 and visit[i][j]==0:
            visit[i][j]=1
            dfs(i,j)
            cnt+=1

print(cnt)

#2. 미로탈출 => 최단거리 => 큐사용하는 문제
# 최단거리는 갈 수 있는 모든 거리를 갈때 그 이전의 cnt를 기억해두고 상하좌우로 가며 cnt를 하나 증가시키는 문제

from collections import deque

queue_x = deque()
queue_y = deque()
queue_cnt = deque()

n,m= map(int, input().split())

map_list =[]
visit=[]
for i in range(0,n):
    map_list.append(list(map(int,input())))
    list_=[0]*m
    visit.append(list_)

#동빈이는 항상 (0,0)에 존재한다고 설정하고 n-1,m-1이 항상 탈출구 위치임

cnt=0

def bsf():
    while True:    
        x = queue_x.popleft()
        y = queue_y.popleft()
        cnt = queue_cnt.popleft()
        #print(x,y,cnt)

        if x==n-1 and y==m-1:
            print(cnt)
            return

        if x-1>=0 and map_list[x-1][y]==1 and visit[x-1][y]!=1:
            queue_x.append(x-1)
            queue_y.append(y)
            queue_cnt.append(cnt+1)
            visit[x-1][y]=1
        if x+1<n and map_list[x+1][y]==1 and visit[x+1][y]!=1:
            queue_x.append(x+1)
            queue_y.append(y)
            queue_cnt.append(cnt+1)
            visit[x+1][y]=1
        if y-1>=0 and map_list[x][y-1]==1 and visit[x][y-1]!=1:
            queue_x.append(x)
            queue_y.append(y-1)
            queue_cnt.append(cnt+1)   
            visit[x][y-1]=1
        if y+1<m and map_list[x][y+1]==1 and visit[x][y+1]!=1:
            queue_x.append(x)
            queue_y.append(y+1)
            queue_cnt.append(cnt+1)
            visit[x][y+1]=1
    
queue_x.append(0)
queue_y.append(0)
queue_cnt.append(1)    
visit[0][0]=1       

bsf()