[코드트리] DFS

DFS

 DFS는 그래프 자료구조에서 정의 된다. 그래프를 탐색하는 방법으로 Depth First Search의 약자, [깊이 우선 탐색]이라고 한다. 그래프의 원소를 타고 내려가서(깊게) 탐색한 후 끝 지점을 만나면, 다시 이전으로 돌아가서 다시 탐색을 한다.

 

 DFS는 재귀함수를 이용해서 구현하며, 이미 방문한 원소(지점이라고 하자.)는 다시 방문하지 않아야 효율이 좋기 때문에, 이전에 방문한 지점은 어떠한 처리를 해서 더는 방문하지 않도록 하자.

 

어떠한 처리는 visited라는 배열을 만들어서 지점에 해당하는 배열의 원소에 체크를 해두는 것이다.

 

DFS를 이용하게 되는 그래프는 인접 행렬 혹은 인접 리스트로 나타낼 수 있다.

 

DFS를 이용하여 문제를 풀어보자.

코드트리 : https://www.codetree.ai/missions/2/problems/graph-traversal/introduction?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 N개의 정점과 M개의 간선이 있는 그래프를 입력받아서 도달할 수 있는 정점의 수를 구하는 문제로, 기본 구현에서 입력받아 그래프를 자료구조를 형성해야한다. 또한, 정점을 방문할 때 만난 정점의 갯수를 세야한다.(visited 배열을 이용해서 중복은 없다.)

코드

#include <bits/stdc++.h>
using namespace std;

void DFS(int vertex, vector<int>* graph, bool* visited, int* vinum) {
    int k = graph[vertex].size();
    for (int i = 0; i < k; i++) {
        int curv = graph[vertex][i];

        if (!visited[curv]) {
            (*vinum)++;
            visited[curv] = true;
            DFS(curv, graph, visited, vinum);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int snums, enums;
    int N, M;
    cin >> N >> M;

 
    vector<int>* graph = new vector<int>[N + 1];
    bool* visited = new bool[N + 1];



    int* start_points = new int[M];
    int* end_points = new int[M];

    memset(visited, false, sizeof(bool) * N + 1);

    for (int i = 0; i < M; i++) {
        cin >> snums >> enums;
        graph[snums].push_back(enums);
        graph[enums].push_back(snums);
    }
    int root_vertex = 1;
    visited[root_vertex] = true;
    int vinum = 0;
    int* ptr = &vinum;
    DFS(root_vertex, graph, visited, ptr);
    cout << vinum << '\n';


    return 0;
}

 

 

===========================================================================================

 2차원 격자가 주어져 있는 상황에서 특정 시작점으로부터 갈 수 있는 모든 지점을 방문하는 DFS 탐색 구현. 그리고 이를 이용한 문제.

코드트리 : https://www.codetree.ai/missions/2/problems/determine-escapableness-with-2-ways?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드

 

#include <bits/stdc++.h>
using namespace std;
int order = 1;
bool InRange(int x, int y,int N, int M) {
    return 0 <= x && x < N && 0 <= y && y < M;
}
bool CanGo(int x, int y,int N, int M, bool ** visited,int ** grid) {
    if (!InRange(x, y,N,M))
        return false;
    if (visited[x][y] || grid[x][y] == 0)
        return false;
    return true;
}

void DFS(int x, int y,int N,int M,int** answer,bool** visited,int** grid) {
    int dx[2] = { 1,0 };
    int dy[2] = { 0,1 };
    
    for (int i = 0; i < 2; i++) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];
        if (CanGo(new_x, new_y,N,M,visited,grid)) {
            answer[new_x][new_y] = order++;
            visited[new_x][new_y] = 1;
            DFS(new_x, new_y,N,M,answer,visited,grid);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M; //N은 행의 수, M은 열의 수, 세로 가로.
    cin >> N >> M;
    //cout << N << M;
    int** grid;
    grid = new int*[N+1];
    for (int i = 0; i < N+1; i++) {
        grid[i] = new int[M+1];
    }

    int** answer;
    answer= new int*[N+1];
    for (int i = 0; i < N+1; i++) {
        answer[i] = new int[M+1];
        fill_n(answer[i], M, 0);
    }
    answer[0][0] = 1;
    bool** visited;
    visited = new bool*[N+1];
    for (int i = 0; i < N+1; i++) {
        visited[i] = new bool[M+1];
        fill_n(visited[i], M, false);
    }
    visited[0][0] = 1;
    for (int i = 0; i < N; i++) {
        fill_n(grid[i], M, 0);
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
        }
    }
    DFS(0, 0, N, M, answer, visited, grid);
    /*for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << visited[i][j] << " ";
        }
        cout << '\n';
    }*/
    if (!visited[N-1][M-1]) {
        cout << 0;
    }else{
        cout << 1;
    }
        
    

    return 0;
}

 주석 처리한 부분은 visited로 어떤 경로로 갈 수 있는지 확인할 수 있는 코드 부분이다. 출력과는 상관 없으므로 주석 처리했다.