인접 행렬(1)

좋아요 우리는 아주 차근차근 열심히 공부하고 있어요.

 

코딩 잘하는 사람이 되는 그날까지 열심히해봅시다!

화이티잉!

우리는 저번 포스팅에서 그래프와 트리 이진트리에 대해서 배웠었죠?

 

그렇다면 간선 정점 뭐 이런 개념을 알고 있는데, 이것을 컴퓨터에게 전달할 때 어떻게 전달을 해야 할까요?

 

그럴때 사용하는게 인접행렬, 인접리스트 이렇게 두가지가 있습니다.

인접이란 연결되어있다는 소리입니다.

 

오늘은 인접행렬을 공부할거에요!

 

 

인접 행렬

인접 행렬은 그래프에서 정점과 간선의 관계를 나타내며 bool 타입의 정사각형 행렬을 의미합니다.
정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가지는데, 0은 두 정점 사이의 경로가 없음을 의미합니다.
또한 1은 두 정점 사이의 경로가 있음을 의미하는 그런 행렬입니다.

 

그림을 보면서 이해해봅시다.

이러한 무방향(양방향) 그래프가 있습니다.

그렇다면 이것을 행렬으로 표현하면 어떻게 될까요?

이와 같은 행렬이 나오게 됩니다.

보시면 1과 1은 안이어지죠? 당연하죠 자기 자신은 안이어지니

2와 1은 이어져있습니다.

3과 4 또한 1이랑 이어져 있습니다.

이런식으로 행렬을 나타내는 것을 인접행렬이라고 합니다.

한마디로 연결이 되어있으면 1 아니면 0 입니다.

즉 arr[from][to] = 1 or 0이라는 소리입니다.

예를 들어 1(from)에서 2(to)까지의 접점이 있냐라고 물어봤을 때

arr[1(from)][2(to)] = 1이라는 값이 나오니 접점이 있다라는 소리입니다.

접점이 있다라는 소리는 경로가 있다라는 의미겠죠?

 

이러한 이차원 배열의 탐색 코드를 구현을 해야 합니다.

그렇다면 이것을 코드 방식으로 생각해봅시다.

i랑 j를 붙여놨을 때 아 for문이라는 생각이 나죠?

bool arr[4][4] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 1},
    {1, 0, 1, 0},
};

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        // i를 중심으로 j를 본다.
        // i == 0 => j == 0 ~ n까지
        // i == 1 => j == 0 ~ n까지
    }
}

이러한 y(i)를 중심으로 기반을 검색을 할 수 있습니다.

위 그림과 같이 빨주노초 순서대로 검색을 합니다.

 

다음에 또 포스팅하겠습니다 :)