99클럽 코테 스터디 25/99일차 TIL #그래프(미들러)

 

 

 

 

DFS(깊이 우선 탐색) 알고리즘: 기초 개념과 2D 그리드에서의 활용

깊이 우선 탐색(DFS, Depth-First Search)은 그래프나 트리에서 널리 사용되는 탐색 알고리즘이다. DFS는 시작 노드에서 출발해 가능한 한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 단계로 돌아와 다른 경로를 탐색하는 방식으로 동작한다. 이 글에서는 DFS의 기초 개념과 함께, 2D 그리드에서의 활용 방법을 설명한다.

1. DFS의 기본 개념

DFS는 그래프나 트리에서 주어진 시작 노드에서 출발하여 모든 노드를 방문하는 알고리즘이다. DFS는 일반적으로 재귀적으로 구현되며, 다음과 같은 기본 구조를 갖는다.

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

 

위 코드에서 graph는 그래프를 나타내며, node는 현재 탐색 중인 노드를 의미한다. visited는 이미 방문한 노드를 추적하기 위한 집합(set)이다. DFS는 현재 노드를 방문 처리한 후, 연결된 모든 이웃 노드를 재귀적으로 탐색한다.

2. DFS의 2D 그리드에서의 활용

DFS는 2D 그리드에서도 유용하게 사용된다. 2D 그리드는 행(row)과 열(column)로 구성된 2차원 배열이며, 각 셀은 특정 좌표 (x, y)로 접근할 수 있다. DFS를 활용하여 그리드 내에서 특정 경로를 탐색하거나, 연결된 영역을 찾는 등의 작업을 수행할 수 있다.

2D 그리드에서의 DFS 구현은 다음과 같은 형태를 갖는다.

def dfs(grid, x, y, visited):
    if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
        return
    if (x, y) in visited or grid[x][y] == '#':
        return
    
    visited.add((x, y))
    print(f"Visited: ({x}, {y})")
    
    dfs(grid, x + 1, y, visited)  # 아래로 이동
    dfs(grid, x - 1, y, visited)  # 위로 이동
    dfs(grid, x, y + 1, visited)  # 오른쪽으로 이동
    dfs(grid, x, y - 1, visited)  # 왼쪽으로 이동

이 코드는 그리드의 특정 좌표 (x, y)에서 출발하여 상하좌우로 이동하며 탐색을 진행한다. 방문한 셀은 visited 집합에 추가되어 다시 방문하지 않도록 한다.

3. 조건문을 통한 유효성 검사

DFS를 2D 그리드에서 사용할 때는 좌표의 유효성을 확인하는 것이 중요하다. 다음 조건문을 통해 그리드 범위를 벗어난 좌표나 이미 방문했거나 벽으로 표시된 셀에 대한 탐색을 중지할 수 있다.

if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
    return

x < 0, y < 0: 그리드의 범위를 벗어난 좌표를 처리한다.
x >= len(grid), y >= len(grid[0]): 그리드의 오른쪽 경계 또는 아래쪽 경계를 벗어난 좌표를 처리한다.
이 조건문은 그리드 범위 내에서만 탐색이 이루어지도록 보장한다.

4. 탐색 경로의 기록과 반환

DFS를 수행하면서 탐색한 경로를 기록하고 반환하는 방법도 있다. 이는 경로를 추적하거나 분석할 때 유용하다. 다음은 탐색 경로를 기록하여 반환하는 예제 코드이다.

def dfs_path(grid, x, y, visited, path):
    if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
        return
    if (x, y) in visited or grid[x][y] == '#':
        return
    
    visited.add((x, y))
    path.append((x, y))
    
    dfs_path(grid, x + 1, y, visited, path)
    dfs_path(grid, x - 1, y, visited, path)
    dfs_path(grid, x, y + 1, visited, path)
    dfs_path(grid, x, y - 1, visited, path)

    return path

visited = set()
path = dfs_path(grid, 0, 0, visited, [])
print("DFS 탐색 경로:", path)

이 코드는 그리드의 (0, 0)에서 출발하여 가능한 경로를 모두 탐색하고, 탐색한 경로를 리스트로 반환한다.

5. 결론

DFS는 그래프와 2D 그리드에서 강력한 탐색 도구이다. 2D 그리드에서의 DFS는 좌표의 유효성 검사와 방문 처리, 경로 기록을 통해 다양한 문제를 해결할 수 있다. 이 글에서 다룬 내용을 통해 DFS의 기본 개념과 2D 그리드에서의 활용 방법을 이해할 수 있을 것이다.