DFS와 BFS 기초

그래프 문제를 해결할 때 DFS와 BFS는 필수적인 알고리즘입니다.

DFS는 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 후 백트래킹을 통해 다른 경로를 탐색합니다.

BFS는 너비 우선 탐색으로, 현재 노드의 모든 인접 노드를 탐색한 후 다음 레벨의 노드를 처리합니다.

98. 모든 접근 가능한 경로 찾기

1번 노드에서 5번 노드로 가는 모든 경로를 찾는 문제입니다. 인접 행렬로 그래프를 구성하고, 경로를 기록하는 배열과 결과를 저장하는 배열을 사용합니다.

void depth_search(const vector& adjacency_matrix, int current_node, int target, vector<int>& current_path, vector& result) {
    if (current_node == target) {
        result.push_back(current_path);
        return;
    }
    for (int neighbor = 1; neighbor <= adjacency_matrix.size(); ++neighbor) {
        if (adjacency_matrix[current_node][neighbor] == 1) {
            current_path.push_back(neighbor);
            depth_search(adjacency_matrix, neighbor, target, current_path, result);
            current_path.pop_back();
        }
    }
}

99. 섬의 개수 세기

상하좌우 방향으로 연결된 땅이 하나의 섬을 형성합니다. 방문 여부를 확인하는 배열을 사용합니다.

int directions[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void dfs(const vector& grid, vector& visited, int x, int y) {
    if (visited[x][y] || grid[x][y] == 0) return;
    visited[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int next_x = x + directions[i][0];
        int next_y = y + directions[i][1];
        if (next_x >= 0 && next_x < grid.size() && next_y >= 0 && next_y < grid[0].size()) {
            dfs(grid, visited, next_x, next_y);
        }
    }
}

int count = 0;
for (int i = 0; i < grid.size(); ++i) {
    for (int j = 0; j < grid[0].size(); ++j) {
        if (!visited[i][j] && grid[i][j] == 1) {
            ++count;
            dfs(grid, visited, i, j);
        }
    }
}

100. 최대 섬 면적 계산

섬 중 가장 큰 면적을 찾는 문제입니다. DFS로 현재 섬의 크기를 카운트합니다.

int area_count = 0;
void calculate_area(const vector& grid, vector& visited, int x, int y) {
    if (visited[x][y] || grid[x][y] == 0) return;
    visited[x][y] = true;
    ++area_count;
    for (int i = 0; i < 4; ++i) {
        int next_x = x + directions[i][0];
        int next_y = y + directions[i][1];
        if (next_x >= 0 && next_x < grid.size() && next_y >= 0 && next_y < grid[0].size()) {
            calculate_area(grid, visited, next_x, next_y);
        }
    }
}

101. 고립 섬의 전체 면적

모든 경계에 닿지 않은 섬의 면적을 계산합니다. 경계에서부터 탐색하여 연결된 땅을 수중에 잠깁니다.

void explore_island(vector& grid, int x, int y) {
    grid[x][y] = 0;
    for (int i = 0; i < 4; ++i) {
        int next_x = x + directions[i][0];
        int next_y = y + directions[i][1];
        if (next_x >= 0 && next_x < grid.size() && next_y >= 0 && next_y < grid[0].size() && grid[next_x][next_y] == 1) {
            explore_island(grid, next_x, next_y);
        }
    }
}

102. 고립 섬 침몰

고립 섬을 0으로 변경하는 문제입니다. 경계에서 시작하여 연결된 땅을 잠급니다.

void sink_island(vector& grid, int x, int y) {
    grid[x][y] = 2;
    for (int i = 0; i < 4; ++i) {
        int next_x = x + directions[i][0];
        int next_y = y + directions[i][1];
        if (next_x >= 0 && next_x < grid.size() && next_y >= 0 && next_y < grid[0].size() && grid[next_x][next_y] == 1) {
            sink_island(grid, next_x, next_y);
        }
    }
}