[알고리즘] DFS, BFS

DFS : 깊이 우선 탐색, stack자료구조 사용

BFS : 너비 우선 탐색, queue자료구조 사용

from collections import deque

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

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

dfs(graph,1,visited)
bfs(graph,1,visited)

문제 - 음료수 얼려먹기

def bfs(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
    bfs(x-1,y)
    bfs(x+1,y)
    bfs(x,y-1)
    bfs(x,y+1)
    return True
  return False
graph=[]
n,m = map(int,input().split())
for i in range(n):
  graph.append(list(map(int,input().split())))

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

print(result)

 

문제 - 섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

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

while True:
    m, n = map(int, input().split())
    if(n==0 and m==0):
        break
    graph=[]
    for i in range(n):
        graph.append(list(map(int, input().split())))
    result=0
    for i in range(n):
        for j in range(m):
            if dfs(i,j)==True:
                result += 1
    print(result)

 

 

bfs를 사용한 최단거리:

문제 - 미로 탈출

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))