인접행렬(2)

회사 퇴근하고 작성하려니 몸이 스르르 녹네요.

자고싶당

그래도 해야죠

ㅎㅎㅎㅎㅎ

 

자 아무튼

우리는 인접행렬에 대한 개념을 조금 배워봤어요.

 

그렇다면 한 번 다시 해봅시다.

만약에

정점의 갯수가 10개인 그래프가 있습니다.

이를 인접행렬로 표현하면 어떻게 될까요?

 

bool arr[10][10];

가 되겠죠.

 

그러면 0번부터 9번까지 10개인 노드가 있습니다.

1 - 2 / 1 - 3 / 3 - 4라는 경로가 있습니다.

이를 인접행렬로 표현한다면 어떻게 될까요?

bool arr[10][10];

arr[1][2] = 1;
arr[2][1] = 1;
arr[1][3] = 1;
arr[3][1] = 1
arr[3][4] = 1;
arr[4][3] = 1;

이렇게 되겠죠?

 

그럼 이어서 0번부터 방문안한 노드를 찾고 해당 노드부터 방문하고 연결된 노드를 이어서 방문하여 출력하는 재귀함수를 구현하려고 합니다.

 

아래 코드를 보죠.

#include <iostream>

using namespace std;

bool arr[10][10], visited[10];

void solve(int from)
{
    // 방문을 먼저 했다는 표시
    visited[from] = 1;
    cout << from << '\n';
    
    for (int i = 0; i < 10; ++i)
    {
        // 방문했으면 continue
        if (visited[i])
            continue;
        
        // 이 아래는 방문을 안했다는 표시니 다시 재귀함수 시작
        if (arr[from][i])
        {
            solve(i);
        }
    }
}

int main()
{
    arr[1][2] = 1;
    arr[2][1] = 1;
    arr[1][3] = 1;
    arr[3][1] = 1;
    arr[3][4] = 1;
    arr[4][3] = 1;
    
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            // arr[i][j]에 값이 있을 때 visited를 통해 방문했는지 체크
            // 0은 곧 false니 방문하지 않았다는 뜻
            if (arr[i][j] && visited[i] == 0)
            {
                solve(i);
            }
        }
    }
}

 

주석으로 설명처리 했습니다.

 

설명해보겠습니다.

 

일단 i = 0 부터 시작하고 j도 0부터 시작합니다.

그럴 때 arr[i][j]의 값이 true 즉 간선이 있는지 확인합니다.

없다면 지나가겠죠?

그러면 i가 1이고 j가 2일때는 어떨까요?

arr[1][2]라는 값은 1 즉 true가 들어가 있죠?

그렇다면 visited라는 배열을 검사합니다.

물론 처음이니 값은 당연히 false(0)일 겁니다.

그렇다면 solve재귀함수를 실행하게 되고

인자에는 1이 들어가게 됩니다.

루트노드가 들어가게되네요.

 

from에는 1이라는 인덱스가 들어가게 되며

visited[from] = 1;

재귀함수에서 이 부분이 제일 먼저 실행이 될텐데요.

방문을 했으니 당연히 true로 변경 시켜줘야 하죠.

 

그다음 반복문입니다.

for (int i = 0; i < 10; ++i)
{
    if (visited[i])
        continue;
        
    if (arr[from][i])
    {
        solve(i);
    }
}

그렇다면 visitied[i]는 방문을 했는지 체크를 합니다.

 0은 방문을 안했더라도 arr 즉 정점에 존재하지 않으니 solve라는 함수가 실행되지 않습니다.

그렇다면 1(from)과 관련되고 방문이 되지 않은 인접행렬은 무엇이 있나요?

[1][2]와 [1][3]이 있습니다.

 

트리를 보자면 이렇습니다.

1과 연결된 것은 2와 3입니다.

그렇다면 2먼저 방문하고 2와 연결된 간선이 있는지 체크하고 없으면 다시 돌아갑니다.

그렇다면 ++i가 되어 3으로 시작해서 다시 3과연결된 간선을 찾게 됩니다.

 

방문의 순서는 이렇습니다.

너무 이해가 안가신다면 디버깅을 찍어서 활용해봅시다.

 

디버깅좀

 

이런 식으로 탐색하는 재귀함수 코드를 짤 수 있습니다.

 

끄으틍