[Python] BFS(너비 우선 탐색), DFS(깊이 우선 탐색)

BFS : 1 - 2 - 3 - 8 - 7 - 4 - 5 - 6

DFS : 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

 

	BFS ( 넓이 우선 탐색 )	DFS ( 깊이 우선 탐색 )
동작 원리	큐	스택
구현	큐 자료구조	재귀 함수
문제	길 찾기	구역 개수 찾기
Tip	while queue 상하좌우 이동	재귀 함수 탈출 조건 상하좌우 재귀 이중 for
	dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]	상 : x-1, y   하 : x+1, y 좌 : x, y-1   우 : x, y+1
	범위 제어 (1, 1) 시작 : x < 0 or y < 0 or x >= n or y >= m (0, 0) 시작 : x <= -1 or y <= -1 or x >= n or y >= m

 

미로 찾기

import sys
from collections import deque

input = sys.stdin.readline

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

maze = []
for _ in range(n):
    maze.append(list(map(int, input().rstrip())))

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

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 ny < 0 or nx >= n or ny >= m:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                
                maze[nx][ny] = maze[x][y] + 1
                queue.append((nx, ny))
    
    return maze[n-1][m-1]


print(bfs(0, 0))

음료수 얼려먹기

import sys

input = sys.stdin.readline

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

graph = []
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))

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

result = 0

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

print(result)