DFS/BFS

1.  스택 예제

 

stack=[]
stack.append(5)
stack.append(3)
stack.append(2)
stack.pop()
print(stack) #최하단 원소부터 출력한다.
print(stack[::-1]) #최상단 원소부터 출력한다.

 

2. 큐 예제

from collections import deque
#큐 구현을 위해서 deque 라이브러리 사용
queue=deque()

queue.append(5)
queue.append(3)
queue.append(2)
queue.append(7)
queue.popleft() #큐는 선입선출이다.

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾼다.
print(queue)

3. 재귀함수 예제

 

def recursive_function():
  print('재귀함수를 호출합니다.')
  recursive_function()
  

recursive_function()

def recursive_function(i):
  if i==100:
    return
  print(i, '번째 재귀 함수에서',i+1,'번째 재귀 함수를 호출합니다.')
  recursive_function(i+1)
  print(i,'번째 재귀 함수를 종료합니다.')

recursive_function(1)

4. 팩토리얼 예제

 

#반복적으로 구현한 n!
def factorial_iterative(n):
  result=1
  #1부터 n까지의 수를 차례대로 곱한다.
  for i in range(1,n+1):
    result*=i
  return result

#재귀적으로 구현한 n!
def factorial_recursive(n):
  if n<=1: #n이 1이하인 경우에는 1을 반환한다.
    return 1
  #n!=n*(n-1)!를 그대로 코드로 작성
  return n*factorial_recursive(n-1)


 #각각의 방식으로 구현한 n! 출력(n=5)


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

 

5. 인접 행렬 방식 예제

인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

 

 

# 인접 행렬 방식 예제

INF=99999
#2차원 리스트를 이용해 인접 행렬 표현
graph=[
  [0,7,5],
  [7,0,INF],
  [5,INF,0]
]

print(graph)

 

6. 인접 리스트 방식 예제

인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

 

# 인접 리스트 방식 예제

#행이 3개인 2차원 리스트로 인접 리스트 표현
graph=[[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))

#노드 2에 연결된 노드 정보 저장
graph[2].append((0,5))

print(graph)

7. DFS 예제

 

#DFS 메서드 정의
def dfs(graph,v,visited):
  #현재 노드를 방문처리한다.
  visited[v]=True
  print(v,end=' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문한다.
  for i in graph[v]:
    if not visited[i]:
      dfs(graph,i,visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현한다.(2차원 리스트)

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

#각 노드가 방문된 정보를 리스트 자료형으로 표현한다.(1차원 리스트)
visited=[False]*9

#정의된 DFS 함수를 호출한다.
print("방문한 노드의 순서")
dfs(graph,1,visited)

8. BFS 예제

from collections import deque
#BFS 메서드 정의
def bfs(graph,start,visited):
  #큐 구현을 위해 deque 라이브러리 사용
  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

#각 노드가 연결된 정보를 리스트 자료형으로 표현한다.(2차원 리스트)

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

#각 노드가 방문된 정보를 리스트 자료형으로 표현한다.(1차원 리스트)
visited=[False]*9

bfs(graph,1,visited)

 

9. 음료수 얼려 먹기

# N*M 크기의 틀에서 아이스크림 만들기

#N,M을 공백으로 구분하여 입력받는다. 
n,m=map(int,input().split())

#2차원 리스트의 맵 정보 입력받기
graph=[]
for i in range(n):
  graph.append(list(map(int,input())))

  #DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문한다.


 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)
     dfx(x+1,y)
     dfx(x,y+1)
     return True
     
  return False

  #모든 노드(위치)에 대하여 음료수를 채운다.
result=0
for i in range(n):
  for i in range(m):
    #현재 위치에서 DFS를 수행한다.
    if dfs(i,j)==True:
      result+=1

print("만들 수 있는 아이스크림의 총 갯수")
print(result)

10. 미로탈출

#미로 탈출

from collections import deque
#N,M을 공백으로 구분하여 입력받기
n,m=map(int,input().split())

#2차원 리스트의 맵 정보 입력받기
graph=[]
for i in range(n):
  graph.append(list(map(int,input())))

#이동할 네 방향 정의(상하좌우)
dx=[-1,1,0,0]
dy=[0,0,-1,1]

#BFS 소스코드 구현
def bfs(x,y):
  #큐 구현을 위해 deque 라이브러리 사용
  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 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]

#BFS를 수행한 결과를 출력한다.
print(bfs(0,0))