[TAVE/이코테] ch05 DFS/BFS | 개념 정리 | 실전 문제

참고자료: 이것이 코딩테스트다

꼭 필요한 자료구조 기초

• 탐색(Search): 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 자료구조(Data Structure): 데이터를 표현하고 관리하고 처리하기 위한 구조

👉🏻DFS와 BFS를 공부하기 위해서는 자료구조 스택과 큐에 대한 사전지식이 필요하다. 

• 스택: 선입후출 혹은 후입선출 구조
• 큐: 선입선출 구조

👉🏻파이썬에서 큐를 구현할 때는 collections 모듈의 deque 자료구조를 활용하면 좋다. deque에 대한 내용은 아래 링크를 참조하자!

https://itwithruilan.tistory.com/67

[TAVE/파이썬 알고리즘] Ch10 | 데크, 우선순위 큐 - 개념 정리

✅재귀함수

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

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

👉🏻해당 코드를 실행하면 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력한다.

👉🏻무한 반복을 피하기 위해 재귀함수의 종료 조건을 꼭 명시해야 한다. 

탐색 알고리즘 DFS/BFS

👉🏻DFS와 BFS에 대한 내용은 아래 링크를 참조하자!

https://itwithruilan.tistory.com/61

[TAVE/파이썬 알고리즘 인터뷰] Ch12 | 그래프 - 개념 정리

실전 - 음료수 얼려 먹기

👉🏻위 그림은 다음과 같이 주어진 3 x 3 크기의 얼음 틀을 그래프 형태로 모델링 한 것이다.

001
010
101

👉🏻0인 값이 상, 하, 좌, 우로 연결되어 있는 노드를 묶으면 위 그림과 같이 세 묶음이 나온다. 이는 DFS를 이용해 해결할 수 있다.

1. 특정 지점의 주변 상, 하, 좌, 우를 살피고 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하면 연결된 모든 지점을 방문할 수 있다.
3. 1~2번 과정을 모든 노드에 반복하면서 방문하지 않은 지점의 수를 센다.

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

graph = []

for i in range(n):
    graph.append(list(map(int, input())))

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)
        dfs(x + 1, y)
        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)

실전 - 미로 탈출

👉🏻시작 지점에서 가까운 노드부터 차례대로 탐색하는 BFS가 효과적인 방법이다.

from collections import deque

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

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

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

result = 0
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] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    return graph[N - 1][M - 1]
print(bfs(0,0))

👉🏻deque에 계속해서 시작점을 넣어주어 더 이상 시작점이 없을 때(도착했을 때)까지 반복문을 돌려 탐색한다.

✍🏻길이 통하는 곳을 찾을 때마다 1씩 더하기 때문에 단계가 모두 끝나고 그래프 마지막 요소를 출력하면 최단 경로가 나온다.