깊이 우선 탐색(DFS, Depth First Search)

이거는 좀 진지하게 적을 생각입니다.

이거 매우 중요하거든요

 

진짜 열심히 쓸거에요 이거 이쁘게 찬란하게

음!

 

 

깊이 우선 탐색(DFS, Depth First Search)

깊이 우선 탐색 DFS라고도 불립니다.
DFS는 그래프를 탐색할 때 쓰는 알고리즘인데요.
어떤 노드부터 시작해서 인접한 노드들을 재귀적으로 방문해서 방문한 정점은 다시 방문하지 않고 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.

즉, 그래프를 탐색할 때 쓰는 알고리즘 중 하나입니다.

루트노드부터 시작해 왼쪽부터 제일 멀리있는 노드까지 순차적으로 검사한 다음 다시 올라와서 분기점에서 다시 내려와서 검사하는 알고리즘입니다.

분기점

각 분기점은 어디냐면 자식이 2개인 노드인 것들이 분기점이라고 합니다.

근데 DFS의 핵심은 방문한 정점은 다시 방문하지 않습니다.

 

그렇기에 가능한 제일 먼 노드를 탐색을 먼저하기에

깊이 우선 탐색이라고 합니다.

 

수도코드(Pseudocode)

수도코드란 프로그램의 로직을 표현하기 위해 쓰이는 코드입니다.
어떤 알고리즘이 어떠한 로직을 갖고있는지 나타내기 위한 코드인데요.
저도 이거 대학교 때 책에서 본 것 같아요.
까먹었음 근데.

 

DFS의 수도코드만 이해한다면 DFS전체를 이해한거나 다름없기 때문에

수도코드를 보여드리겠습니다.

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

 

아 맞다 진지하게

 

여기서 u는 from입니다.

adj는 인접리스트라고 하죠.

 

DFS(u, adj)

이 부분은 DFS는 어떠한 함수겠죠?

u는 from입니다.

0부터 시작한다면

u는 0이 되는 겁니다.

adj는 그래프를 담고있는 어떠한 컨테이너중 하나겠죠.

 

u가0이라고 가정할 때 방문을 먼저 체크해줍니다.

u.visited = true

 

그리고 0과 연결된 간선들을 반복문을 통해 순회해서 검사합니다.

for each v ∈ adj[u]

∈ 이거는 adj[u]에 포함한 애들

즉 adj라는 그래프에 0에 관련된 애들을 순회하는 겁니다.

그래서 그 관련된 v가 방문하지 않았으면?

if v.visited == false

 

그 정점부터 시작해 다시 DFS라는 함수를 거치게 되며 from은 다시 v가 됩니다.

DFS(v, adj)

 

 

이것을 코드로 작성해봅시다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[6];
int visited[6];

void DFS(int u)
{
    visited[u] = 1;
    cout << u << '\n';
    
    for (int v : adj[u])
    {
        if (visited[v] == 0)
        {
            DFS(v);
        }
    }
    
    cout << u << "에서 시작된 함수가 종료됨\n";
    
    return;
}

int main()
{
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    // 1부터 시작
    DFS(1);
}

구현은 위와 같습니다.

 

우리는 수도코드를 보면 바로 코드를 작성할 수 있어야 합니다.

 

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

DFS의 수도코드를 보며 한 번 작성해보죠.

 

void DFS(int u)
{
    // 방문
    visited[u] = true;
    
    // 들어온 정점에 관련된 애들을 순회
    for (int i : adj[u])
    {
        // 방문하지 않았다면
        if (visited[i] == false)
            DFS(i);
    }
    
    return;
}

저도 한 번 안보고 작성해봤습니다.

 

다들 한 번 작성해보세요.

 

DFS을 구현하는 방법은 총 2가지가 있어요.

1. 방문했는지에 대한 구현 방법
2. 무작정 구현

 

방문했는지에 대한 구현 방법

void DFS(int here)
{
    visited[here] = true;
    
    for (int there : adj[here])
    {
        if (visited[there] == false)
            DFS(there);
    }
}

 

visited라는 배열 또는 리스트를 통해 방문했는지에 대한 체크 여부를 한 다음 탐색합니다.

 

 

무작정 구현

void DFS(int here)
{
    if (visited[here] == true) 
        return;
        
    visited[here] = true;
    
    for (int there : adj[here])
    {
        DFS(there);
    }
}

방문했는지에 대한 체크는 순회해서 하지 않고 재귀함수 첫번째부터 체크를 하는 방식입니다.

 

 

이제 문제를 하나 같이 풀어보고 마치도록하죠.

 

문제.
맵의 세로길이 N과 가로길이 M이 주어집니다.
이어서 N * M의 맵이 주어집니다.
캐릭터는 상하좌우 네방향으로 길을 방문하여 갈 수 있는 곳은 다 방문하였는지에 대한 지역의 개수를 출력하는 문제입니다.
1은 갈 수 있는곳 0은 갈 수 없는 곳입니다.

 

이 문제를 보았을 때 저번 포스팅의

연결된 컴포넌트가 떠올라야 합니다.

 

해보죠.

 

#include <iostream>
#include <vecetor>

using namespace std;

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };

int adj[100][100];

bool visited[100][100];

int N, M;

int answer;
void DFS(int _y, int _x)
{
    visited[_y][_x] = true;
    
    // 상하좌우를 검색하기 위해 4번 반복
    for (int i = 0; i < 4; ++i)
    {
        ny = _y + dy[i];
        nx = _x + dx[i];
        
        if (ny < 0 || nx < 0 || ny >= N || nx >= N)
            continue;
            
        //  갈수 있는 곳이면?
        if (adj[ny][nx] == 1 && visited[ny][nx] == false)
        {
            DFS(ny, nx);
        }
    }
    
    return;
}

int main()
{
    // 일단 N과 M을 입력받자.
    cin >> N >> M;
    
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            // 갈 수 있는 곳과 없는 곳을 입력
            cin >> adj[i][j];
        }
    }
    
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (adj[i][j] == 1 && visited[i][j] == false)
            {
                answer++;
                DFS(i, j);
            }
        }
    }
    
    // 방문한 곳의 거리를 출력
    cout << answer << '\n';
}

 

만약에 입력이

5 5
1 0 1 0 1
1 1 0 0 1
0 0 0 1 1
0 0 0 1 1
0 1 0 0 0

이렇게 들어왔다고 치면

답은 4가 나와야 합니다.

 

총 4개의 지역을 가능한 곳까지 다 방문한 체크를 출력하기 때문이죠.

 

 

DFS 어려울 줄 알았는데 간단하죠?

다들 이제 DFS에 관련된 깊이 우선 탐색이란 문제를 보면 바로 쉽게 풀 수 있을 거구, 그게 안된다면 이 포스팅을 다시 확인해봐야 합니다!

 

 

진짜 끄으으읕