DFS & BFS

1. 스택 & 큐 구현
   1. 스택(Stack)
   2. 큐(Queue)
2. 깊이 우선 탐색(DFS)
3. 넓이 우선 탐색(BFS)
   1. BFS 문제 1. 미로 탈출

스택 & 큐 구현

스택(Stack)

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

stack.pop()
stack.pop()

print(stack)

결과 => [1, 2, 4]

💡 역순으로 정렬하기 => stack[::-1]

큐(Queue)

from collections import deque

queue = deque()

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

print(queue)

결과 => deque([2, 3, 4])

💡 역순으로 정렬하기 => queue.reverse()

깊이 우선 탐색(DFS)

• ```py graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7], ]

visited = [False] * 9

def dfs(graph,v,visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph,i,visited)

dfs(graph,1,visited)

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

## DFS 문제 1. 얼음 얼려 먹기
문제 설명: 
```py
ice_maker = []

n, m = map(int,input("크기: ").split())

for i in range(n):
    ice_maker.append(list(map(int,input(f"{i+1}번줄: "))))

# DFS
result_dfs = 0

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

for i in range(n):
    for j in range(m):
        if iceAge_dfs(i,j) == True:
            result_dfs +=1


print(result_dfs)

넓이 우선 탐색(BFS)

• 가까운 노드부터 우선적으로 탐색하는 알고리즘 ```py visited = [False] * 9

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) ``` 결과> 1->2->3->8->7->4->5->6

BFS 문제 1. 미로 탈출

문제 설명:

• N x M 크기의 직사각형 형태의 미로를 괴물을 피해 탈출해야 한다.
• 현재 위치는 (1,1)이고 미로의 출구는 (N,M)에 위치하며 한 칸씩 이동 가능하다.
• 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다.

  탈출하기 위한 최소 칸의 개수를 구하세요. ⚠️ 시작칸과 마지막 칸은 항상 1이다.

---

참고 이코테 2021