서린이의 기술 블로그

Q. 인접행렬을 기반으로 탐색하기

조건 1.

정점은 0번부터 9번까지 10개의 노드가 있다. 1 - 2 / 1 - 3 / 3 - 4 라는 경로가 있다. (1번과 2번, 1번과 3번, 3번과 4번은 연결되어있다.) 이를 인접행렬로 표현한다면?

조건 2.

0번부터 방문하지 않은 노드를 찾고, 해당 노드부터 방문, 연결된 노드를 이어서 방문해서 출력하는 재귀함수를 만들고 싶다면 어떻게 해야할까? 또한, 정점을 방문하고 다시 방문하지 않게 만드려면 어떻게 해야할까?

정답코드

#include<bits/stdc++.h>
using namespace std;
const int V = 10;
bool a[V][V], visited[V];
void go(int from) {
    visited[from] = 1;
    cout << from << '\n';
    for(int i = 0; i < V; i++) {
        if(visited[i]) continue;
        if(a[from][i]) {
            go(i);
        }
    }
}

int main() {
    a[1][2] = 1; a[1][3] = 1; a[3][4] = 1;
    a[2][1] = 1; a[3][1] = 1; a[4][3] = 1;
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; i++) {
            if(a[i][j] && visited[i] == 0) {
                go(i);
            }
        }
    }
}

출처 : 인프런 강의, CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조, 강사 : 큰돌

1. 그래프 : 정점과 간선으로 이루어져 있는 자료구조

    1-1. 정점 : 노드

    1-2. 간선 : 단방향 간선, 양방햔 간선(= 무방향 간선)

2. 인접행렬 : 정점과 간선을 컴퓨터에게 그래프로 알려주기 위한 방법

      - 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미

      - 정사각형 행렬의 각 요소가 0 또는 1이라는 값을 가짐을 의미

      - 표기법

         a[from][to] = 1 : from ~ to로가는 간선이 있음, 0이면 없음

         ex:)

         a[0][1] = 1, 0에서 1로 가는 간선이 존재

         a[2][0] = 1, a[2][1] = 1 ..

         0  1  1  1

         1  0  1  0

         1  1  0  0

         1  0  0  0

         - c++ 코드 예시

x, y = 4;

bool a[x][y] = {
   {0, 1, 1, 1},
   {1, 0, 1, 0},
   {1, 1, 0, 0},
   {1, 0, 0, 0},
};



# a[0][1] = 1
# a[2][1] = 1
# a[3][0] = 1
# ...

for(int i = 0; i < x; i++) { # y를 중심으로 x를 본다 (= 가로로 탐색)
	for(int j = 0; j < y; j++) {
        if(a[i][j]) {
            cout << i << "부터 " << j << "까지 경로가 있습니다.\n";
            // 해당 정점(=i)으로부터 탐색하는 로직
            bfs(i);
            dfs(i);
        }
    }
    
}

출처 : 인프런 강의, CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조, 강사 : 큰돌

1. 연결리스트(linked list)

연결리스트는 노드로 감싸진 요소를 인접한 메모리 위치가 아닌, 독립적으로 저장하며 각 노드는 next 또는 next, prev라는 포인터로 서로 연결된 선형적인 자료구조

Data는 Node로 감싸져 있고, 가장 처음을 Head라고 한다.

2. 노드

노드는 단일 연결 리스트 기준으로 data, 그리고 노드와 노드를 잇게 만드는 next라는 포인터로 이루어져 있습니다.

class Node {
public:
    int data;
    Node* next; # 포인터
    Node(){
    	data = 0;
        next = NULL;
    }
    Node(int data){
    	this->data = data;
        this->next = NULL;
    }
};

연결리스트에서 삽입, 삭제는 O(1)의 시간 복잡도를 가진다. (연결을 끊고, 삽입하거나 제거한 후 연결하면 되기 때문)

연결리스트에서 접근, 탐색은 O(n)의 시간 복잡도를 가진다. (직접 접근이 안되고 1부터 n까지 접근해야하기 때문)

3. 이중연결리스트

이중연결리스트는 prev, next 두개의 포인터(양방향)으로 연결되어 있음

4. 원형연결리스트(Circular Linked List)

마지막 노드와 첫번째 노드가 연결되어 원을 형성, 싱글리스트 또는 이중연결리스트로 이루어진 2가지 타입의 원형연결리스트가 있음

  4-1. 원형싱글연결리스트 : Tail(끝)이 Head로 연결되어있는 구조

  4-2. 원형이중연결리스트 : Head -> Tail, Tail -> Head 모두 연결되어있는 구조

  4-3. c++ 예시 코드

#include <bits/stdc++.h>
using namespace std;
list<int> a;
void print(list <int> a) {
    for(auto it : a) cout << it << " ";
    cout << '\n';
}
int main() {
    for(int i = 1; i <= 3; i++) a.push_back(i); # 1 2 3
    for(int i = 1; i <= 3; i++) a.push_front(i); # 3 2 1
    
    auto it = a.begin(); it++;
    a.insert(it, 1000); # 3과 2사이에 1000을 삽입
    print(a); # 3 1000 2 1 1 2 3
    
    it = a.begin(); it++;
    a.erase(it); # 1000 제거
    print(a); # 3 2 1 1 2 3
    
    a.pop_front(); # 맨 앞 3 제거
    a.pop_back(); # 맨 뒤 3 제거
    print(a); # 2 1 1 2
    
    cout << a.front() << " : " << a.back() << '\n'; # 2 : 2
    a.clear(); # 연결리스트를 모두 소거
    return 0;
}

# 출력
# 3 2 1 1 2 3
# 3 1000 2 1 1 2 3
# 3 2 1 1 2 3
# 2 1 1 2
# 2 : 2

5. 랜덤접근과 순차적 접근

  5-1. 순차적 접근 : 시작부터 순차적으로 접근을 하는 자료구조

    ex:) linked list

    O -- O -- O --> O --> ... --> O // O(n) 시간복잡도

  5-2. 랜덤 접근 : 직접 접근이라고 하며, 임의의 인덱스에 직접 접근할 수 있는 자료구조

    ex:) array, vector

    a[3] => 4, a[100] => 5 // O(1) 시간복잡도

출처 : 인프런 강의, CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조, 강사 : 큰돌