DFS & BFS

jurin·2020년 12월 2일

알고리즘

목록 보기

5/8

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 책과 강의를 보고 정리한 글입니다.
강의 출처 : https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

DFS (Depth-First Search)

깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 스택 자료구조(혹은 재귀 함수)를 이용한다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

DFS는 인접한 노드가 여러개 있을 수 있기 때문에 어떤 노드부터 방문할지를 결정하기 위한 기준이 필요하다. 문제의 요구에 따라 이 기준은 달라진다. 번호가 낮은 인접 노드부터 방문한다고 가정하자.

탐색 순서 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

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

파이썬에서는 그래프를 표현하기 위해 2차원 리스트를 활용한다. 일반적으로 그래프 문제가 출제되면 노드의 번호가 1번부터 시작하기 때문에 인덱스 0의 경우 빈 리스트로 설정해주고, 1번 인덱스부터 해당 노드의 인접한 노드가 무엇인지 리스트 형태로 담아준다. visited 리스트도 총 8개의 노드가 있지만 인덱스 0은 사용하지 않는 것으로 설정하고 9개로 만들어준다.

BFS (Breadth-First Search)

너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘으로 큐 자료구조를 이용한다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

인접한 노드들을 큐에 넣고 하나씩 빼면서 방문한다.

탐색 순서 : 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6
거리가 가까운 순부터 방문하는 것을 확인할 수 있다. 거리가 1인 2, 3, 8을 먼저 방문하고 거리가 2인 7, 4, 5를 방문 후 거리가 3인 6을 방문한다.

음료수 얼려먹기

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구분이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

이 문제는 연결 요소(connected component) 찾기이다.

입력 조건

첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1<=N,M<=1,000)
두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다.

[해결 아이디어]
DFS 혹은 BFS로 해결할 수 있다. 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다.

3 x 3 크기의 얼음 틀이 있다고 가정하자

모든 노드에 대해 DFS와 BFS를 이용해서 방문 처리가 이루어지는 지점에 대해서만 카운트를 하면 전체 연결 요소가 몇 개인지 알 수 있다.

DFS로 풀기
1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 방문한다.
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복해서 연결된 모든 지점을 방문한다.
3. 모든 노드에 대해 1~2번 과정을 반복하고, 방문하지 않은 지점의 수를 카운트한다.

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


# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

print(graph)


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


print(result)

재귀적으로 상, 하, 좌, 우에 대해 호출되는 dfs 내용들은 return값을 사용하지 않기 때문에 그냥 단순히 연결된 모든 노드에 대해 방문 처리를 수행하기 위한 목적으로 작성한 것이다. 시작점 노드만 result 값을 증가시키는 것이다.

미로 탈출

N x M 크기의 직사각형 형태의 미로에는 괴물들이 있다. 캐릭터의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하고, 한 번에 한 칸씩 이동한다. 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라.
(시작 칸, 마지막 칸 포함)

[입력 조건]

첫째 줄에 두 정수 N,M(4<=N,M<=200)이 주어지고 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)이 주어진다. 시작 칸과 마지막 칸은 항상 1이다.

[해결 아이디어]
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하기 때문에 (1, 1)에서 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.

매번 새로운 노드를 방문할 때 이전까지의 거리 +1로 표시를 해주면서 방문한다. 그래서 BFS를 수행했을 때 1씩 증가하는 형태로 마지막까지 도달하여 최단거리를 구한다.

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.append((x, y))

    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        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] == 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))