[자료구조] 인접 행렬과 인접 리스트 문제 풀이 2

[자료구조] 인접행렬 (adjacency list) 출력 문제 풀이 (tistory.com)

 

 

[자료구조] 인접행렬 (adjacency list) 출력 문제 풀이

 

위 포스팅의 코드와 이어지는 문제이므로, 현재 포스팅을 읽기 전 위 포스팅을 보고 오길 바란다.

 

 

 

 

 

 

 

앞선 포스팅의 코드 수정을 통해, 입력으로 주어질 vertex a와 b 사이의 path를 찾고 출력해야 하는 문제이다. 

 

 

 

 

가장 먼저 코드 상단에 적을 내용부터 간단히 보겠다.

#define FALSE 0
#define TRUE 1
#define MAX_VERTICES 11

short int visited[MAX_VERTICES]; 
int path[MAX_VERTICES]; 
int found = FALSE;

 

 

visited 배열을 통해, 특정 vertex가 이미 방문했던 vertex인지 그렇지 않은지 구분되도록 한다.

path 배열을 통해, a와 b 사이 지나가야 할 vertex들 (즉 a와 b 사이의 path)를 기록한다.

a에서 b까지의 모든 path를 찾아냈을 때는 found 변수를 TRUE로 설정해 줄 것이다.

 

 

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

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

    Node* arr[MAX_VERTICES] = {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);
            }
        }
    }

    int a, b;
    scanf("%d %d", &a, &b);

    for (int i = 0; i < MAX_VERTICES; i++) {
        visited[i] = FALSE;
    }

    findPath(arr, a, b, 0);

    fclose(f);

    return 0;
}

 

 

main 함수 전체 형태인데, Node 구조체 형태, createNode 함수,  addEdge 함수 등은 지난 포스팅에서 모두 다루었기에 생략하고, 이번 문제의 본론 함수만 짚어보도록 하겠다.

본격적인 함수 호출에 들어가기 전, arr배열과 visited 배열을 초기화해주는 것을 잊지 말자.

 

 

a와 b를 입력받고, a와 b 사이의 path들을 모두 찾아 출력하기 위해 findPath 함수를 호출한다. 

 

 

void findPath(Node *arr[], int x, int y, int depth)
{
    int found = 0;
    Node *w;
    visited[x] = TRUE;
    path[depth] = x;

    if (x == y)
    {

        found = 1;
        for (int i = 0; i <= depth; i++)
        {
            printf("%d ", path[i]);
        }

        return;
    }

    for (w = arr[x]; w; w = w->next)
    {
        if (!visited[w->vertex] && found == 0)
        {
            dfs(arr, w->vertex, y, depth + 1);
        }
    }
}

 

 

findPath 함수의 전체 형태이다. 전체적으로 dfs (deep first search)방법을 따르고 있다. 

 

 

arr[v]는 노드 v의 인접 노드들을 연결한 리스트 형태로 저장이 되어 있을 것이다. 

 

 

우선 findPath 함수가 호출되었을 경우, 변수 "v"는 무조건 path에 속하게 된다. 따라서 가장 먼저 visited[v]=TRUE와 path[depth]=v부터 적어준다. 또한 findPath 함수가 호출되었다는 건 path가 하나 추가되었다는 것과 같으므로, 매 findPath 호출마다 depth++ 해준다.  

 

 

---

 

 

dfs를 호출했을 때, 이번의 x 값이 최종 y의 값과 동일할 경우! found 변수를 1로 바꾼 뒤, 지금까지 찾은 모든 path 배열의 변수들을 for문을 통해 출력해준다. 그리고 return;을 취한다. return을 취하더라도 재귀 호출 if문에서는 found==0의 조건을 걸어두었기 때문에 추가적으로 dfs 호출이 일어날 일은 없을 거다.

 

 

---

 

 

위 문제에서 중요한 것

 

1. path 배열의 존재. 지나온 모든 길을 출력해야 하므로 필수적.

2. depth 변수의 존재. path 배열 요소들을 카운팅해주는 역할. (findpath의 매개변수로도 들어감 유의)

3. found 변수를 통한 통제. 정답 값을 찾는 즉시 found를 1로 두고, 기존 조건문에서는 found가 0일 때만 재귀 호출이 일어나도록 장치를 두어 원하는 값만 출력되도록 함.