홈 [Algorithm] 코딩테스트 알고리즘 07 - DFS/BFS
포스트
취소

[Algorithm] 코딩테스트 알고리즘 07 - DFS/BFS

게시 2022-05-10 업데이트 2022-10-16
By 19tak

본 포스팅은 “이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)을 바탕으로 공부한 내용을 정리한 것입니다.

  1. 탐색
  2. 주요 개념
    • 스택
    • 큐
    • 재귀함수
  3. DFS
  4. BFS
  5. 실전 문제 1
    • 음료수 얼려 먹기
  6. 실전 문제 2
    • 미로 찾기

1. 탐색

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룬다.

대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다.

이를 제대로 사용하려면 기본 자료구조 스택, 큐와 재귀 함수에 대한 이해가 전제되어야한다.

2. 주요 개념

자료구조란 ‘데이터를 표현하고 관리하고 처리하기 위한 구조’를 의미한다.

  • 삽입 (Push) : 데이터를 삽입한다.
  • 삭제 (Pop) : 데이터를 삭제한다.
  • 오버플로 (Overflow) : 자료구조가 수용할 수 있는 데이터 크기가 가득 찬 상태에서 삽입 연산
  • 언더플로 (Underflow) : 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산

스택

가장 최근에 들어간 데이터가 가장 먼저 나오는 선입후출 (First In Last Out) 또는 후입선출 (Last In First Out) 구조.

보통 deque 내장 모듈을 활용한다.

큐

가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출 (First In First Out) 구조.

역시 통상적으로 deque 내장 모듈로 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12

from collections import deque

dq = deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 가장 왼쪽에 원소 삽입
dq.pop() # 가장 오른쪽 원소 반환
dq.clear() # 모든 원소 제거
dq.copy() # 덱 복사
dq.count(x) # x와 같은 원소의 개수 반환
dq.reverse() # 원소를 역순으로
dq.rotate(n) # n 만큼 우측으로 회전시킨다. 음수일경우 왼쪽으로 회전.

리스트 자료형으로 변경하고자 한다면 list() 사용.

재귀함수

재귀함수 Recursive Functino은 자기 자신을 다시 호출하는 함수이다.

보통 파이썬 인프리터는 호출 횟수 제한이 있어 재귀의 최대 깊이를 초과하면 오류가 발생한다.

RecursionError: maximum recursion depth exceeded while pickling an object

재귀 함수를 사용할 때는 종료 조건을 꼭 명시해야한다. if문을 활용.

컴퓨터의 구조 측면에서 재귀 함수는 스택 자료구조와 같다.

따라서 스택을 사용하는 알고리즘 상당수는 재귀함수로 간편하게 구현될 수 있다.

재귀 함수는 재귀식을 소스코드로 옮기며 간결함의 이점이 있고, 다이나믹 프로그래밍으로도 연결된다.

3. DFS

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

스택 자료구조에 기초한다.

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

그래프

노드(Node), 간선(Edge)으로 표현되고 노드를 정점(Vertex)이라고도 한다.

그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다.

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

코딩 테스트에서는 크게 다음의 두가지 방식으로 표현한다.

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

메모리 측면에서 인접 행렬은 메모리가 불필요하게 낭비

인접 리스트는 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

DFS 구현 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 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 함수 호출
dfs(graph, 1, visited)

4. BFS

BFS는 Breath First Search, 너비 우선 탐색이라 하며, 가까운 노드부터 탐색하는 알고리즘이다.

선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다.

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

시간 복잡도는 O(N), 일반적으로 실제 수행시간이 DFS보다 좋은 편이다.

재귀 함수로 DFS를 구현하면 시스템 동작 특성상 실제 프로그램 수행 시간이 느려질 수 있다고 한다. 스택 라이브러리를 활용해 시간 복잡도를 완화하는 테크닉 필요. 코테에서는 BS로 하자.

BFS 구현 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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 함수 호출
bfs(graph, 1, visited)

5. 실전 문제 1

음료수 얼려 먹기

N x M 크기의 얼음틀에 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시.

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

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

  • 첫째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1000)
  • 둘째 줄부터 N+1 줄까지 얼음 틀의 형태가 주어진다.
  • 뚫려있는 부분은 0, 막힌 부분은 1이다.
  • 한번에 만들 수 있는 아이스크림의 개수를 출력한다.

0으로 연결된 그룹 수를 세라는 것 같다.

DFS로 해결한다.

  1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문.
  2. 방문 지점에서 다시 상하좌우를 살펴보며 반복하면 연결된 모든 지점을 방문할 수 있다.
  3. 위의 두 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

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

print(result) # 정답 출력

너무 어렵다….

6. 실전 문제 2

미로 탈출

N x M 크기의 직사각형 형태의 미로에 갇혀 있다.

(1,1)에서 출구 (N,M) 까지 한번에 한칸씩 이동할 수 있다.

괴물이 있는 곳은 0, 없는 곳은 1로 표시 되어있다. 움직여야 하는 최소 칸의 개수를 구하시오.

칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다.

  • 첫째 줄에 두 정수 N, M (4 <= n, M <= 200). 다음 N 개 줄에는 각각 M개의 정수로 미로의 정보.

BFS를 이용해서 해결한다.

시작 지점부터 가까운 노드를 차례대로 탐색하기에 BFS 수행한 모든 노드의 값을 거리 정보로 넣는다.

특정 노드 방문 하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다.

단순히 우측하단으로 이동하는 것만을 요구하기 때문에 시작 위치의 재방문을 고려하지 않아도 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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):
    # 큐(Queue) 구현을 위해 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))

참고

“이것이 취업을 위한 코딩테스트다 with 파이썬” - (한빛미디어, 나동빈 지음)

Study, Algorithm
Python Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.
최근 업데이트
바로가기