2주차 개념 #4-1. 인접행렬(adjacency matrix)

2주차 개념 #4-1. 인접행렬(adjacency matrix)

우리가 지금까지 그래프라는 걸 배웠죠.

정점과 간선의 집합인 그래프를 컴퓨터에게 알려주려면 어떻게 해야 될까요?

아니 이제 정점과 간선이라는 개념들은 알겠어. 그런데 정점과 간선으로 연결된 이러한 그래프가 있다고 컴퓨터에게 알려주려면 어떻게 해야될까요?

두 가지 방법이 있습니다.

첫 번째는 인접행렬, 두 번째는 인접리스트 라는 게 있습니다.

여기서 인접이라는 것은 연결되어 있다는 거예요.

자, 오늘은 인접행렬과 인접리스트 중에서 인접행렬을 설명을 해드릴 거예요.

그 전에 한 개 짚고 넘어갈 게 있는데, 뭐냐면 우리가 앞서서 단방향 간선에 대해서 배웠죠?

이렇게 하나의 간선만 있는 게 뭐? 단방향 간선이다.

근데 만약에 하나 더 있어. 그럼 이거를 양방향 간선이다 라고 했죠.

이제 우리가 이러한 그래프를 볼 건데 이거는 여러분 화살표가 없죠. 화살표가 없는 간선을 무방향 간선 이라고 해요.

무방향 간선은요. 양방향 간선과 똑같다 라고 생각을 하시면 돼요. 양방향 간선이 무방향 간선이다. 무방향 간선이 양방향 간선이다. 라고 생각을 하셔도 됩니다.

자 방향이 없는 게 무방향인데, 이게 양방향, 두 개 다 방향이 있는 간선을 가지고 있다라는 의미도 된다라는 거예요.

자 이제는 인접행렬을 들어가 보도록 할텐데,

인접행렬이라는 것은 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬이에요.

저희가 뭘 할 거냐면 아까 보여드렸던 그림이

이렇게 연결되어 있었죠? 이거를 인접행렬로 나타낼 건데 인접행렬, bool 타입의 정사각형 행렬을 만들 거예요.

일단 한번 만들어 볼게요.

이렇게 노드 별로, 마지막 노드까지 만약에 4까지 있으면 4까지 만드는 거예요. 근데 이게 3번까지 밖에 없기 때문에 이렇게 만든 거예요. 이러한 정사각형 행렬, 지금 보시면 행과 열이 같은 길이를 가지죠. 그래서 정사각형이에요.

자 그리고 여기서 이러한 특징을 부여할 겁니다.

뭐냐면, 이 행렬을 a라고 할 거에요. 만약에 a[from][to] = 1이면, from 정점에서 to 라는 정점까지 가는 간선이 있다라고 할 거에요. 만약에 그러한 간선이 없으면 0이라고 할 겁니다.

1 또는 0이라는 값을 가지는 booleam 정사각형 행렬을 만든 거예요.

자, 한번 적용을 시켜볼게요. 0과 1, 이거 간선 있어요, 없어요? 있죠.

그러면 여기다가 1, 1 적어요. 둘 다 있으니까 양방향 간선인 거예요. 그래서 a[0][1] = 1, 0에서 1까지는 간선이 있기 때문에 이렇게 표기를 하는 거예요.

계속해서 색칠을 해나가면 이런 식의 모양이 될 겁니다.

그러면 여기서 의문점이 하나 생기죠. 이 나머지 빈칸은 뭘까요? 다 연결이 안 된 거죠.

일단 자기 자신을 잠깐 보도록 할 텐데, 이 자기 자신을 나타내는 이 부분 있잖아요. 이 중앙열, 이 부분은 뭐냐면 사이클을 의미합니다.

예를 들어서 이런 식의 자기 자신을 도는 사이클을 가진 그래프가 있어요. 이거 같은 경우는 중양열에서 [1][1] 부분이 1이 되는 거예요. 근데 이런 사이클이 이 그래프 내에서는 없죠.

그래서 1이 아닌 나머지 부분들은 간선이 없으니까 0으로 채워줍니다.

다시 정리하자면, from 이라는 정점에서 to 라는 정점까지 연결되어 있으면 1이구요. 연결되어있지 않으면 0인거에요. 이게 바로 인접행렬 이라는 거에요.

인접행렬은 그냥 이런 행과 열의 길이가 같은 정사각형 행렬을 만든 거예요. 여기다가 어떠한 의미를 부여한 거냐면, from 이라는 정점에서 to 라는 정점까지 간선이 있으면 1, 없으면 0이라는 속성을 부여한 게 바로 인접행렬이라고 하는 거예요.

면접관이 이렇게 질문할 수가 있어요.

"인접행렬이 뭐죠?" 그러면 이렇게 답하시면 됩니다.

인접행렬이란 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미합니다. 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하는데요. 0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미합니다. 이렇게 하면 "역시 자네야!"

그래서 이러한 그래프를

이렇게 표현한 것까지 해봤어요.

우리가 또 하나 짚고 넘어가야 될 게 있는데, 우리가 2차원 배열을 탐색할 때요. 2차원 배열을 결국에는

이러한 행렬을 기반으로 코드를 구현해야 된단 말이에요. 이러한 행렬을, 이런 2차원 배열을 탐색하는 코드를 구현을 해야 돼요.

구현하는 방법이 2가지가 있어요. 두 가지밖에 없는데 뭐냐면,

이게 Y축이고요. 이게 X축 이잖아요.

그래서 y를 i, x를 j 라고 해서 for i = 0부터, 그 다음에 이 안에다가 j = 0부터, 코드로 볼게요.

지금 이러한 정사각형 행렬이 있죠. 2차원 배열로 나타낸 모습입니다.

이걸 어떻게 구현하냐?

이렇게 할 수 있어요. 지금 보시면은 여기 i, j. 그러니까 이거는 i라는 걸 중심으로 j를 보는 거죠.

이렇게 i가 0일 때 j는 0부터 1까지. i가 1일 때 j는 0부터 1까지.

이런 식으로 i를 중심으로 j를 보는 거죠.

즉, y를 중심으로 x를 보는 거죠. 근데 이렇게 해도 되고요.

이렇게 해도 돼요.

뭐냐면, for j = 0부터, 그 안에 for i = 0 이렇게. 그러면 x를 중심으로 y를 보게 돼요.

그러면 이렇게 탐색하게 되는 거죠.

제가 처음에 보여드렸던 건

이렇게 탐색하게 됐던 거거든요. 이 두 가지의 방식이 있다라는 거예요. 근데 여러분 우리 앞으로는 y를 중심으로 하는 것을 기반으로 합시다. 이게 왜 그러냐면요. C++에서는 이러한 2차원 배열이 만들어졌을 때 행 별로 캐싱이 돼요.

그래서 이렇게 탐색하는 게 조금은 더 빠릅니다.

그래서 앞으로는 이렇게 y축을 중심으로 x축을 탐색하는 게 좋다라는 거를 알려드렸습니다.

---

그래서

이거를

이렇게 만들었습니다.

그래서 잘 맞게 만든 걸 볼 수 있죠.

그래서 이렇게 코드로 구현하는 것까지 얘기를 해봤는데 우리가 이걸 어떻게 쓰냐면,

바로 이런 식으로 씁니다.

이렇게 만들어놓은 다음에

이렇게 쓰여요. 이렇게 y를 중심으로 탐색하면서 만약에 i로부터 j까지의 간선이 있다고 하면 그 i라는 정점부터 bfs, dfs 이런 식으로 쓰인다는 거예요.

우리가 지금까지 인접행렬, 그리고 인접행렬의 개념, 그리고 인접행렬을 코드로 구현하는 것까지 얘기를 해봤습니다.