[이코테] 3장 DFS/BFS, 음료수 얼려 먹기, 미로찾기

스택

• 선입후출, LIFO
• 입구와 출구가 동일한 형태
• append(), pop()은 시간복잡도가 O(1)

stack = []
stack.append(5) # [5]
stack.append(2) # [5,2]
stack.append(3) # [5,2,3]
stack.pop() # [5,2]
stack.append(6) # [5,2,6]

print(stack[::-1]) # [6,2,5] 가장 위에 있는 원소부터 출력

큐

• 선입선출, FIFO
• 리스트를 이용할 수 있지만 시간복잡도가 효율적이지 않아서 라이브러리 이용

from collections import deque

queue = Queue()

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

print(queue) # deque([2,3,4])
queue.reverse() # 역순으로 바꾸기
print(queue) # deque([4,3,2])

DFS

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(or 재귀함수) 이용
• 경로를 탐색할 때, 한 방향으로 갈 수 있을때까지 계속 간다
• 더 이상 갈 수 없다면? 다른 방향으로 다시 탐색 진행
• 더이상 방문하지 않은 인접 노드가 없을 때 스택에서 꺼낸다

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 = [
    [],   # index = 0
    [2,3,8],  # 1번 노드
    [1,7],  # 2번 노드
    [1,4,5], # 3번 노드
    [3,5], # 4번 노드
    [3,4], # 5번 노드
    [7],
    [2,6,8], # 7번 노드
    [1,7] # 8번 노드
]

# false가 9개 담겨있는 리스트
visited = [False] * 9

dfs(graph, 1, visited)

재귀함수

• 자기 자신을 다시 호출하는 함수
• 재귀 함수를 문제풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음
• 재귀함수가 메모리(stack구조)에 쌓이는 방식
• 순서 1(검정)→ 2(빨강) → 3(초록)

재귀함수 설명

def recursive_function(i):
    # 100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
    print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
    recursive_function(i + 1)
    print(i, '번째 재귀함수를 종료합니다.')

recursive_function(1)

BFS

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘, 멀리 떨어져 있으면 나중 탐색
• 큐 자료구조 이용

from collections import deque

def bfs(graph, v, visited):
     # 현재 노드를 방문 처리
    queue = deque([start])
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue: # while queue니까 queue안에 원소가 들어있을 때
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 2차원 리스트
graph = [
    [],  # index = 0
    [2,3,8], # 1번 노드
    [1,7], # 2번 노드
    [1,4,5], # 3번 노드
    [3,5], # 4번 노드
    [3,4], # 5번 노드
    [7],
    [2,6,8], # 7번 노드
    [1,7] # 8번 노드
]

# false가 9개 담겨있는 리스트
visited = [False] * 9

bfs(graph, 1, visited)

DFS vs BFS 문제 분류

둘 다 이용 가능

• 그래프의 모든 정점을 방문한다.

DFS

1. 경로의 특징을 저장한다.

2. 경로 이동 시 가중치가 붙거나 제약이 있다. 

-> DFS 이용! BFS는 경로의 특징을 가질 수 없다.

BFS

1. 최단거리

-> BFS는 너비를 우선으로 탐색하기 때문에 현재 노드에서 가까운 곳부터 찾아 경로 탐색 시 먼저 찾는 해답이 곧 최단거리가 된다.

실전문제) 음료수 얼려 먹기

• input : 인접행렬

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

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

def dfs(x,y):
  if x >= n or x < 0 or y >= m or y < 0:
    return False  # 종료
  if graph[x][y] == 0: # 만약, 0이라면? 연결된 애들 중에서 0인애들 다 확인하면서 스택에 쌓기!
    graph[x][y] = 1
    dfs(x-1, y) # 상 먼저 이쪽으로만 이동할 수 있으면 계속 탐색한다(DFS) 여기서 더이상 이동 불가능하고 탐색이 끝났을 때 '하'쪽으로 간다..
    dfs(x+1, y) # 하
    dfs(x, y-1) # 좌
    dfs(x, y+1) # 우
    return True
    else:
    return False # 있는 이유? - else, graph[x][y] != 0 느낌이었다.
# 이걸 안해도 반환 값이 없음. non이기 때문에 
# 그래도 반환값을 적는 것이 좋다! 

result = 0
for i in range(n):
  for j in range(m):
    if dfs(i, j) == True: # 여기서 어쨌든 True가 아니기 때문에 작동하는것
      result += 1

print(result)

실전문제) 미로찾기

• input : 인접행렬
• 모든 거리가 1로 동일한 상태
• 왜 처음 방문하는 경우를 == 1로 설정한 것이 최단거리가 될까?
• ex. 초록색 거리가 검정색 거리보다 길다는 것을 어떻게 인지하지?

→ 거리의 합이 8와 12이 동시에 한곳을 목표로 오고 있는데 8인게 먼저 방문해서 이 칸이 9가 되면 ≠ 1 이므로 12는 오지 못한다. (사진설명)

from collections import deque

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

# 동일
graph = []
for _ in range(n):
  graph.append(list(map(int, input())))
# print(graph)

  # 좌, 우, 상, 하
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 왜 bfs일까??
# 시작 지점에서 가까운 노드부터 차례대로 탐색하기 떄문에
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 graph[nx][ny] == 1: # 처음이면
        graph[nx][ny] = graph[x][y] + 1 # 원래꺼에 1을 더해서 새롭게 담고
        queue.append((nx,ny)) # 새로운길 큐에 append
      if graph[nx][ny] == 0: 
        continue
      if nx < 1 or nx>= n or ny<1 or ny>=m:
        continue
  return graph[n-1][m-1] # 인덱싱 숫자 문제로