3일차 - DFS/BFS

꼭 필요한 자료구조 기초

 

탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

자료구조(Data Structure) : 데이터를 표현하고 관리하고 처리하기 위한 구조

 

스택 : 선입후출 구조(First In Last Out) 또는 후입선출 구조(Last In First Out)라고 한다.

파이썬에서는 list를 통해 append로 삽입, pop을 통해 삭제를 할 수 있다.

# 스택

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)
print(stack[::-1])

 

 

큐 : 선입선출 구조(First In First Out)라고 한다.

파이썬에서는 collections에 있는 deque 함수를 통해 queue를 사용할 수 있다.

보통의 list에는 없는 popleft가 있어서 개인적으로 많이 사용한다.

# 큐 (deque)

from collections import deque

queue = deque()

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

print(queue)
queue.reverse()
print(queue)

 

 

재귀 함수 : 자기 자신을 다시 호출하는 함수를 의미한다.

DFS/BFS를 구현하기 위해 필수적으로 이해해야한다.

파이썬 인터프리터는 1,000번의 횟수 제한이 있지만, 제한을 변경할 수 있다.

아마 프로그래머스 문제를 풀다보면 바꾸는 경우가 종종 있을 것이다.

 

 

 

DFS(Depth-First Search)는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

먼저 그래프(graph)의 개념을 알아야한다.

그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점 (Vertex)이라고도 말한다.

두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다(Adjacent)라고 표현한다.

프로그래밍에서 그래프는 크게 아래 2가지 방식으로 표현할 수 있다.

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

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

 

1) 인접 행렬(Adjacency Matrix)방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.

(다른 언어의 배열(Array)을 파이썬에서는 리스트 자료형으로 표현할 수 있으므로 파이썬은 인접 행렬을 list로 구현한다.)

# 인접 행렬(Adjacency Matrix)
# 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

INF = 999999999

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

이 코드를 살펴보자면,

0번노드는 1번노드(코스트 7)와의 2번노드(코스트 5)와 연결되어있다.

1번노드와 2번노드는 연결되어 있지 않다.

 

 

2) 인접 리스트(Adjacency List)는 '연결 리스트'라는 자료구조를 이용해 구현하는데, Python에서는 리스트 자료형의 append()를 사용한다.

# 인접 리스트(Adjacency List) 

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

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

graph[1].append((0, 7))

graph[2].append((0, 5))

print(graph)

1)인접 행렬과 마찬가지이다.

 

그렇다면 두 방식은 어떤 차이가 있을까?

공간

인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다.

인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.

시간

인접 리스트 방식은 인접 행렬방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.

 

마치 배열과 연결리스트의 차이를 또 보는것 같다.

 

 

DFS는 스택 자료구조를 이용하며 동작 과정을 아래와 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않는 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

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

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(Breadth First Search)는 너비 우선 탐색이라고 부르고, 가까운 노드부터 탐색하는 알고리즘이다.

 

DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하는데, BFS는 그 반대이다.

 

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3) 2번의 과정을 더 이상 수행할 수 없을 때까지를 반복한다.

 

# BFS
from collections import deque

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

bfs(graph, 1, visited)

 

 

	DFS	BFS
동작 원리	스택	큐(deque)
구현 원리	재귀 함수 이용	큐 자료구조 이용

 

 

예제 5-10 음료수 얼려먹기

구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.

구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주.

얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림 개수를 구하는 프로그램을 작성.

 

구멍이 뚫려 있는 연속적인 파트의 갯수를 구하는 문제이다.

같은 영역을 묶어야한다? DFS다.

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.

3. 1~2번 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.

# 얼음틀 사이즈 정보 받아오기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
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 + 1, y)
        dfs(x, y - 1)
        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)

 

 

예제 5-11 미로탈출

말 그대로 미로 탈출이다. 1이 길이고 0이 벽이다. 총 움직인 횟수를 구하는 것이다.

내 생각에는 가장 가까운 지점으로 가야하므로 BFS를 추천하는것 같다.

from collections import deque

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]

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 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]
print(bfs(0, 0))