BFS & DFS

stack = []

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

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

 

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(queue) # 먼저 들어온 순서대로 출력.
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력.

 

def factorial_iterative(n): # 반복적으로 구현
    result = 1
    for i in range(1, n+1):
        result = result * i
    return result

def factorial_recursive(n): # 재귀적으로 구현
    if n<=1:
        return 1
    else :
        return n*factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

 

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

print(gcd(192,162))

def dfs(graph, v ,visited):
    visited[v] = True #방문 처리
    print(v, end=' ')
    for i in graph[v]:
        if visited[i] == False: #아직 미방문이라면
            dfs(graph, i, visited)

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) # 시작 노드=1

 

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 # 방문처리

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

visited = [False] * 9
bfs(graph, 1, visited) # 시작 노드=1

 

def dfs(x,y):

    if x < -1 or x >= N or y <= -1 or y >= M:
        return False

    if graph[x][y] == 0: #미방문시
        graph[x][y] = 1 #방문처리

        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        return True
    else:
        return False #[x][y]가 방문 노드인 경우


N,M = map(int,input().split())

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

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
def bfs(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
            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]


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]

print(bfs(0,0))