[이코테] DFS & BFS 문제 풀이

나동빈님의 이코테 수강 후 정리한 포스팅입니다.
https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

 

 

그래프 탐색 알고리즘 : DFS / BFS

스택 자료구조

먼저 들어온 데이터가 나중에 나가는 형식 = 선입후출

박스 쌓기를 생각하자!

stack = []

stack.append(5) # 오른쪽에서 원소 넣기
stack.pop() # 가장 오른쪽 원소 제거

큐 자료구조

먼저 들어 온 데이터가 먼저 나가는 형식 = 선입선출

대기열을 생각하자!

from collections import deque

queue = deque()

queue.append(5) # 오른쪽에서 원소 넣기
queue.popleft() # 가장 왼쪽 원소 제거
queue.reverse() # 역순으로 바꾸기

재귀 함수

자기 자신을 다시 호출하는 함수

종료 조건을 반드시 명시해야 한다

팩토리얼 구현 예제

# N 입력값을 받으면 N!을 출력
# 팩토리얼 점화식 : N! = N * (N-1)!

N = int(input())

def factorial(N):
    if N == 0 or N == 1:
        return 1
    return N * factorial(N - 1)

print(factorial(N))

최대공약수 계산 (유클리드 호제법) 예제

# 유클리드 호제법을 이용한 최대공약수 계산
# A, B(A > B) 가 있을때 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다

A = int(input())
B = int(input())

def gcd(A, B):
    if A % B == 0:
        return B
    return gcd(B, A % B)

print(gcd(A, B))

DFS (Depth-First-Search)

깊이 우선 탐색

스택 자료구조 또는 재귀 함수 사용

1. 탐색 시작 노드를 스택에 넣고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 (방문 기준은 문제에서 제시됨)
3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복

# DFS : 깊이우선탐색
# 방문 기준 : 숫자가 낮은 노드
# 시작 노드를 스택에 넣고 방문처리
# 노드에서 방문하지 않은 인접노드가 있다면 인접한 노드를 스택에 넣고 방문처리
# 노드에서 인접노드가 모두 방문한 노드라면 해당 노드를 스택에서 꺼냄
#

graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9

def dfs(node):
    # 방문한 노드는 방문 처리
    visited[node] = True
    print(node)

    # 인접노드 순회
    for i in graph[node]:
        # 방문하지 않은 노드는 방문
        if not visited[i]:
            dfs(i)

dfs(1)

BFS (Breadth-First-Search)

너비 우선 탐색

큐 자료구조 사용

1. 탐색 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 넣고 방문 처리
3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복

# 시작 노드를 큐에 넣음
# 큐에서 하나 꺼내서 방문하지 않은 인접한 노드를 큐에 넣음
# 큐에 원소가 다 없어질때까지 수행

from collections import deque

queue = deque()
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
visited = [False] * 9

def bfs(node):
    queue.append(node)
    visited[node] = True
    print(node)

    while queue:
        pop = queue.popleft()

        for i in graph[pop]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                print(i)

bfs(1)

음료수 얼려 먹기

# 0: 뚫려있는 부분 1: 막혀있는 부분
# 얼려진 음료수가 총 몇개인지 구하라

from collections import deque

queue = deque()

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

board = [[int(char) for char in input()] for _ in range(N)]

visited = [[False] * M for _ in range(N)]

drow = [1, -1, 0, 0]
dcol = [0, 0, -1, 1]

def bfs(row, col):
    visited[row][col] = True
    queue.append((row, col))

    while queue:
        pop = queue.popleft()
        pop_row = pop[0]
        pop_col = pop[1]

        for i in range(4):
            new_pop_row = pop_row + drow[i]
            new_pop_col = pop_col + dcol[i]

            if 0 <= new_pop_row < N and 0 <= new_pop_col < M:
                if not visited[new_pop_row][new_pop_col]:
                    if board[new_pop_row][new_pop_col] == 0:
                        visited[new_pop_row][new_pop_col] = True
                        queue.append((new_pop_row, new_pop_col))

count = 0
for row in range(N):
    for col in range(M):
        if board[row][col] == 0 and not visited[row][col]:
            bfs(row, col)
            count += 1

print(count)

미로 탈출

# N x M 미로
# 동빈이의 위치는 (1,1)
# 미로의 출구 (N, M)
# 한번에 한칸씩 이동
# 0: 괴물이 있는 부분, 1: 괴물이 없는 부분
# 미로는 반드시 탈출할수있음
# 탈출하기 위해 움직여야하는 최소 칸의 개수?

from collections import deque

queue = deque()

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

board = [[int(char) for char in input()] for _ in range(N)]

visited = [[False] * M for _ in range(N)]

drow = [1, -1, 0, 0]
dcol = [0, 0, -1, 1]

def bfs(row, col, depth):
    visited[row][col] = True
    queue.append(((row, col), depth))

    while queue:
        pop = queue.popleft()
        pop_row = pop[0][0]
        pop_col = pop[0][1]
        depth = pop[1]

        if pop_row == N - 1 and pop_col == M - 1:
            return depth

        for i in range(4):
            new_pop_row = pop_row + drow[i]
            new_pop_col = pop_col + dcol[i]

            if 0 <= new_pop_row < N and 0 <= new_pop_col < M:
                if not visited[new_pop_row][new_pop_col]:
                    if board[new_pop_row][new_pop_col] == 1:
                        visited[new_pop_row][new_pop_col] = True

                        queue.append(((new_pop_row, new_pop_col), depth + 1))

print(bfs(0, 0, 1))