[자료구조] 인접 행렬과 인접 리스트(adjacency list) 문제 풀이 1

 

 

 

 

 

 

본격적인 문제 풀이에 앞서, adjacency matrix가 무엇인지부터 짚어보도록 하자.

 

 

인접 행렬 (Adjacency Matrix)

인접 행렬은 그래프를 표현하는 방법 중 하나로,

그래프의 모든 노드 쌍에 대해 엣지(간선)의 존재 여부를 나타내는 2차원 배열.

 

 

예를 들어, 다음과 같은 그래프가 있다고 가정해 보자.

 

1 - 2
| \ |
3 - 4

 

 

이 그래프를 인접 행렬로 표현해 본다면 다음과 같다.

 

    1  2  3  4
1 [ 0, 1, 1, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 1, 0, 0, 1 ]
4 [ 1, 1, 1, 0 ]

 

0은 두 노드 사이에 엣지가 없음을, 1은 두 노드 사이에 엣지가 있음을 나타낸다.

 

 

 

 

---

 

 

우리의 문제에서는 이 인접 행렬을 in.txt 파일을 통해 upper diagonal 부분만 입력받았다. 바로 위 행렬만 봐도 알 수 있듯, 인접행렬은 대칭 형태이기 때문에 upper diagonal 부분만 있어도 전체 인접 행렬 모양을 떠올릴 수 있다. 

 

 

입력받은 upper diagnol을 전체 인접 행렬로 만들어 본다면 이러한 형태가 나올 것이다.

 

    1  2  3  4  5
1 [ 0, 1, 1, 0, 1 ]
2 [ 1, 0, 1, 0, 0 ]
3 [ 1, 1, 0, 1, 0 ]
4 [ 0, 0, 1, 0, 1 ]
5 [ 1, 0, 0, 1, 0 ]

 

 

 

이제 인접 행렬의 개념은 알겠는데, 문제처럼 

5 -> n = 5 (노드 개수)
1 1 0 1 1 0 1 0 0 1 -> upper diagonal 부분

 

해당 형태로 입력이 들어오니 뭔가 헷갈린다. 숫자가 일렬로 들어오니 헷갈릴 수 있지만, 자세히 들여다보면 바로 위 행렬의 upper diagnol을 그저 일렬로 나열한 것 뿐이라는 사실을 알 수 있다. 따라서 이는 이중 for문으로 쉽게 입력받을 수 있다.

 

  

    int value=0;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            fscanf(f, "%d", &value);
            if (value == 1) {
                addEdge(arr, i, j);
            }
        }
    }

 

이렇게 말이다. 값이 1일 경우에만 특정 행위를 취해 준다. 이제부터 그 내용을 다루어 보자 !

 

 

 

---

 

 

문제에서, linked adjacency list를 구성하라는 말이 보인다. 코드를 보기 전 내용부터 스포하자면, 

1 - 2
| \ |
3 - 4

 

위와 같은 그래프일 때 노드 1의 adjacency list는 node(1)= 4->3->2 가 된다.

 

노드별로 자신과 인접한 노드들을 자신의 인접 list에 순차적으로 담아주는 모습을 상상하면 된다. 그런데 우리 문제의 경우, 노드 2와 4가 연결되었을 경우 (2,4) (4,2) 두 번을 언급하는 것이 아니라 (2,4) 한 번만 언급하기 때문에, 우리가 알아서 이를 (2)->4, (4)->2 두 가지로 취해주어야 한다. 

 

 

 

가장 먼저, 각 노드의 구조체 모형이다.

typedef struct Node{
    int vertex;
    struct Node *next;
}Node;

 

우리는 시작 전, Node * arr[11];을 선언한다. n개의 노드별로 각각 list 를 만들 것이므로, 각 list의 header값이 담길 장소라고 볼 수 있겠다.

 

 

 

 

 

다음으로는 이 문제의 핵심 코드인, addEdge, 말 그대로 간선을 추가해주는 함수이다. 앞서 말했듯 (2,4)의 입력이 들어왔을 때 어떻게 처리할지를 해결해주는 코드이다.

 

void addEdge(Node* arr[], int i, int j)
{
    Node *newNode = createNode(j);
    newNode->next=arr[i];
    arr[i]=newNode;

    newNode = createNode(i);
    newNode->next=arr[j];
    arr[j]=newNode;

}

 

 

(i,j) 입력이 들어왔을 때 ( 즉 노드 i와 j 사이에 edge가 존재할 때 )

 

1. i의 인접 list에도 j 노드를 담아야 하고, j의 인접 list에도 i 노드를 담아야 한다.

2. 따라서 우선 j 노드를 createNode 함수를 통해 생성한다.

3. 생성한 j 노드의 next는 기존 i list의 최신 노드를 가리키도록 한다. (newNode -> next = arr[i])

4. 생성한 j노드를 i list에 담는다. 

5. i,j 관점을 반대로 하여 2~4 과정을 한 번 더 수행한다.

 

 

---

  

위 내용을 이해했다면,

 

for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            fscanf(f, "%d", &value);
            if (value == 1) {
                addEdge(arr, i, j);
            }
        }
    }

 

 

이 코드를 통해 결론적으로 노드별로 개개인의 인접 list가 생성되었구나를 깨닫게 된다. 

 

 

 

 

최종적으로 아래와 같은 print 함수를 만든다.

void printing(Node* arr[], int n) {
    for (int i = 1; i <= n; i++) {
        Node* temp = arr[i];
        printf("Vertex %d:", i);
        while (temp) {
            printf(" %d ", temp->vertex);
            temp = temp->next;
        }
            printf("\n");
    }
}

 

 

 

그럼 결과적으로 출력값은 문제에서 요구한 바와 같이

 

 

위와 같은 모양으로 나오게 된다. 

 

 

 

 

 

 

전체 정답 코드를 남겨놓으며 포스팅을 마친다.

 

 

 

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int vertex;
    struct Node *next;
}Node;



Node* createNode(int vertex){
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->vertex=vertex;
    newNode->next=NULL;
    return newNode;
}



void addEdge(Node* arr[], int i, int j)
{
    Node *newNode = createNode(j);
    newNode->next=arr[i];
    arr[i]=newNode;

    newNode = createNode(i);
    newNode->next=arr[j];
    arr[j]=newNode;

}




void printing(Node* arr[], int n) {
    for (int i = 1; i <= n; i++) {
        Node* temp = arr[i];
        printf("Vertex %d:", i);
        while (temp) {
            printf(" %d ", temp->vertex);
            temp = temp->next;
        }
            printf("\n");
    }
}

int main()
{
    FILE *f=fopen("in.txt","r");

    int n=0;
    fscanf(f,"%d",&n);


    Node* arr[11]={NULL};

    int value=0;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            fscanf(f, "%d", &value);
            if (value == 1) {
                addEdge(arr, i, j);
            }
        }
    }

    printing(arr,n);

    fclose(f);

    return 0;
}