[코드트리 조별과제] 깊이 우선 탐색[DFS] 기초

흠..

처음 코드트리를 들어갔는데, 마침 조별과제 이벤트를 하더라?

마침 DFS/BFS 기초부터 배울 수 있길래 이번에 정복?을 해보고자 한다.

---

1. Depth-First Search  [약칭 DFS]란?

뭔가 되게 있어 보이지 않는가?

사전적 의미로는 "  맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다."

 

라고 상당히 장황하게 적혀있는데..

우리는 우리 입맛대로, 손쉽게 이해해 보도록 하자.

그냥 한 길만 죽어라 파면서 남는 길이 없을 때까지 반복하는 거다.

 

2. DFS 이해를 위한 예시

2-1. DFS 이해 예시 #1

자.. 아래 사진과 같이 뚫린 지점이 여러 곳 있는 미로가 있다고 하자.

미로 #1

 

우리는 우선 하나의 길을 선택하고, "더 이상 갈 수 있는 길"이 없을 때까지 이동할 것이다.

"1번 입구"를 선택한 상태로 제일 먼저 만나는 길을 중심으로 이동한다고 하면, 아래 색칠 된 부분만큼 이동하게 된다.

미로 #2

 

그럼 한 칸씩 다시 돌아오면서 연결된 다른 길이 있는지 확인한다.

돌아오는 와중에 연결된 길이 또 있으면 그 길이 막힐 때까지 이동한다.

그럼 아래 색칠 된 부분만큼 이동하게 된다.

조금 더 진한 색은 중복으로 이동된 부분으로 보자!

미로 #3

 

이걸 더 이상 이동할 수 있는 경우의 수가 없을 때 까지 반복한다.

각 칸에 있는 숫자는 중복해서 지나간 곳임을 표시했다.

미로 #4

 

이제 시작 지점을 선택했을 때, 그 지점과 연결된 탈출구가 몇 개가 있는지 한 번에 확인할 수 있다. 그렇지?

쉽게 말해서 막힐 때까지 한 길만 쭉 파는 거다. 경우의 수가 존재하지 않을 때까지.

 

"일반적으로 접근할 수 있는 길을 모두 탐색하는 것"

"그래프 계의 완전탐색"

 

그것이 DFS다.

 

2-2. DFS 이해 예시 #2

음... 아직도 모르겠거나 헷갈리면..

전형적인 그래프를 통해 알려주겠다.

 

아래와 같은 트리형 그래프가 있다고 해 보자.

그래프 #1

 

하나의 길만 쭉 파는 형식으로 각 노드에 접근하면, 아래 사진 순서와 같이 이루어지게 될 것이다.

각 노드 안에 쓰여 있는 숫자는 그 노드에 접근한 순서라고 이해하면 된다.

그래프 #2, 3

그래프 #4, 5

 

이 정도면... 이해가 되지 않았을까 싶다.

 

어느 정도 공부를 한 사람이라면, 위 플로우를 봤을 때

아! 재귀를 쓰면 되겠구나!

라고 느낄 수 있을 것이다! 모든 경우를 확인해야 하니까~

이제 실전과 함께 이해를 해 보도록 하자!

 

3. DFS 기본 문제 풀이

3-1. 문제 개요 확인

코드 트리(Codetree)에 좋은 문제가 하나 있더라.

코드트리 문제 #1

 

자, 중요한 점만 짚어보면

문제 ❗
N개의 정점, M개의 간선이 입력 인자로 들어온다.

1번 정점에서 이동을 시작했을 때 도달할 수 있는 정점 수는 몇 개인지를 출력한다. (노드 1번 제외)

 

천천히 한 스탭씩 풀어보자.

입출력 형식은 아래와 같다.

입출력 형식

 

그리고, 본 글에서 서술할 때는 아래의 입출력 예제를 사용하겠다.

3-2. N, M 저장 및 2차원 배열 생성

우선 정점과 간선을 저장하는 2차원 배열이 필요하다.

해당 정점이 어디와 연결되어있는지를 저장하는 배열이 1차원 배열이고,

그러한 1차원 배열을 모아 놓은 것이 2차원 배열이 되도록 구현을 해 보자.

연결되어 있는 것은 "1", 연결되어있지 않으면 0으로 설정하겠다.

목표 배열

C++에서 Vector를 통해 선언을 해줄 것이다.

대충 간단하게 선언해 주자.

아래 코드를 통해 입력의 첫 번째 줄인 N과 M을 저장하고, 그에 맞춘 2차원 배열 공간을 선언했다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> graph(N, vector<int>(N, 0));

	return 0;
}

 

3-2. 배열 내 정점 데이터 입력

자, 그럼 이제 배열에 값을 입력해 주자.

만약 입력이 "1 2"로 들어온다면 1번과 2번 정점에서 서로 연결되어 있다고 표시해 주어야 한다.

아래 코드에서 각 아이템에 -1을 하는 이유는, 입력하는 값이 1부터 시작하여 들어오기 때문이다.

    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x-1][y-1] = 1;
        graph[y-1][x-1] = 1;
    }

 

 

예제 입력을 보면

{1 2} / {1 3} / {2 3} / {4 5} 이렇게 들어왔다.

자, 선언했던 2차원 배열에 데이터를 넣으면 아래와 같이 나오게 될 것이다.

채워진 그래프

 

3-3. 무한 루프 예외처리

자, 그럼 이제 우리는 이 데이터를 기반으로 재귀를 돌려야 한다.

왜냐?

 

처음 DFS를 말할 때
"막힐 때까지 계속 진행한다"라고 했지 않는가.

1번 정점과 2번 정점을 예로 들어보자. 가장 먼저 만나는 길로 진행할 것이다.

문제 풀이중 #1

 

어라!

 

1번 정점에서 연결되었다고 해서 2번 정점으로 이동했는데,

2번 정점에서 처음 만나는 연결점이 1번 정점이라고 한다!

위처럼 진행하면

다시 1번 정점 이동 -> 2번 정점 이동 -> 1번정점 이동 -> 2번정점 이동...

이처럼 무한 반복이 되어버린다.

 

하여 "이미 지나갔던 정점"을 체크할 필요가 있다.

이것도 VECTOR STL로 bool 형 배열을 선언하여 관리해 주도록 할 것이다!

vector<bool> visit;
...
visit.resize(N, false);
visit[0] = true;
...

 

자, 왜 visit [0]은 미리 True로 설정을 하는지 궁금할 수 있다.

처음 문제에서 "1번 정점"에서 시작한다고 했고, 중복되는 건 처리하지 않기로 했지 않는가?

무한 반복과 중복 이동을 막기 위해 visit [0]을 미리 막아놓고 시작하는 거다.

 

3-4. DFS 설계 및 재귀 함수 구현

자,, 그럼 설계를 해보자.

정상적으로 실행된다면, 아래와 같은 순서로 실행되게 될 것이다.

1

2

3

 

눈으로 봤으니, 이제 코드로 구현을 해 보자.

코드에서 구현해야 할 사항은 아래와 같이 될 것이다.

1. 각 정점의 아이템이 1인지 검사한다
2. 아이템이 1이라면, 해당 visit이 FALSE인지 검사한다
3. 만약 visit도 FALSE라면 방문 정점으로 체크(TRUE)하고, 해당 정점을 기준으로 위 과정을 반복한다.
4. 만약 visit이 TRUE라면 해당 아이템을 건너뛴다.

int result = 0;

void DFS(int target, const vector<vector<int>> &gp)
{
    for (int i = 0; i < gp.size(); i++) // 정점 별 아이템 반복
    {
        if (gp[target][i] == 1 && !visit[i]) // 해당 아이템이 1이고, visit하지 않았는지 검사
        {
            result++;			// 방문한 정점 개수 관리!
            visit[i] = true;		// visit 한 정점이라 표시
            DFS(i, gp);			// 해당 정점도 동일하게 동작하도록 설정
        }
    }
}

 

인자로 들어가는 "Target"은 점검하고자 하는 정점 번호가 될 것이고,

gp는 한참 전에 만들었던 2차원 배열인 그래프 데이터가 될 것이다.

여기서 왜 포인터로 만들었는지는... 메모리 관리에 대해 배워야 알 수 있는데, 간단하게 말하자면

 

2차원 배열을 수십 수백 개가 만들어지는 것을 방지하기 위함이다. << 이거 좀 중요하다. 알고리즘 풀이에선..

 

3-5. 실행 결과

DFS() 함수를 실행하고 난 뒤,

전역 변수로 선언한 result를 출력해 주기만 하면 이제 정답! 처리가 될 것이다.

정답입니다!

 

코드 전문은 아래 접은 글을 펼쳐보자.

그래도! 열기 전에 스스로 짜 보는 것을 추천한다!!

codetree-TILs/240718/그래프 탐색 at main · devbini/codetree-TILs

#include <iostream>
#include <vector>
using namespace std;

vector<bool> visit;
int result = 0;

void DFS(int target, const vector<vector<int>> &gp)
{
    for (int i = 0; i < gp.size(); i++)
    {
        if (gp[target][i] == 1 && !visit[i])
        {
            result++;
            visit[i] = true;
            DFS(i, gp);
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> graph(N, vector<int>(N, 0));
    visit.resize(N, false);

    for (int i = 0; i < M; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x-1][y-1] = 1;
        graph[y-1][x-1] = 1;
    }

    visit[0] = true;
    DFS(0, graph);
    cout << result;
    
    return 0;
}

---

4. 마치며

중간에 vector 배열 데이터를 포인터로 넘기는 부분이 있는데,

사실 필자가 그거 때문에 시간초과가 나와서 문제를 틀렸었다.

바본가?

 

프로그램을 짤 때는 알고리즘도 알고리즘이지만,

그 외적인 메모리 관리는 기본적으로 할 수 있어야 한다.

 

자잘 자잘한 것들에서 코드의 가독성과 효율성, 메모리와 시간 복잡도가 크게 바뀔 수 있다는 것을 여러분들은 아셨으면 좋겠네요.

나 부터 잘하자

 

다음부터는 좀 더 신경 쓰고, 조심하도록 합시다!

다들 긴 글 읽고 공부하느라 고생하셨습니다.

다음 글에서 만나요!