내가 그때 이걸 알았더라면

저번 글에 이어 이번 글에서는 그래프를 읽어온 결과를 바탕으로 그래프 상에서 dfs를 해보겠다.

0. 그래프 구조

먼저, 저번 글에서 사용한 그래프 구조를 직접 그리면 다음과 같다.

1. dfs 코드

dfs는 Depth-First-Search의 약자로 현재 정점에서 다음 정점으로 갈 수 있는 경우, 탐색을 계속하며 다음 정점이 없는 경우에는 부모 정점으로 돌아가 다시 갈 수 있는 정점가 있는지 판단한다.

다음 정점이 있는 경우 계속해서 탐색을 하기 때문에 트리에서 탐색할 경우, 루트 노드에서 계속해서 높이를 내려가면서 탐색을 하므로 dfs라는 이름이 붙었다.

코드 전반은 다음과 같다.

int dfs(vector<vector<int>> &graph, vector<int>& visited, int n){
    cout << "Vertex " << n << "\n";
    visited[n - 1] = 1;

    for(int i = 0; i < graph[n - 1].size(); i++){
        int idx = graph[n - 1][i];
        if(!visited[idx - 1]){
            dfs(graph, visited, idx);
        }
    }
    return 0;
}

그래프 정보를 저장하는 이차원 배열 graph와 방문 여부를 저장하는 배열visited, 현재 정점 번호를 저장하는 idx 변수를 매개변수로 가진다.

재귀함수를 이용해 코드를 구현했으며(스택을 이용해도 가능하다) 정점을 방문할 시 현재 정점에 방문처리를 한다.

그리고 현재 정점에 연결된 다른 정점들을 방문했는지 체크하며, 만약 방문하지 않았다면 그 정점을 방문한다.

결과는 다음과 같다.

8번 정점에서 5번 정점으로 가는 이유는, 8번 정점에서 5번 정점으로 갈 수 있기 때문이다.

dfs는 높이가 위에서 아래로 내려가는 것만이 아니라, 다음에 갈 수 있는 정점이 있는지 여부를 가지고 탐색을 계속한다.

이 글에서는 fstream 라이브러리를 이용한(C++11 이상 버전 권장, 버퍼 객체 bool 타입으로 변환 가능해서) 파일 입출력 예제를 다뤄보겠다.

수업에서 배운 dfs, bfs, 다익스트라 알고리즘 등을 복습할 겸 C++로 코드를 짜보았다.

1. include

먼저 기본 입출력에 필요한 iostream, 그래프 정보를 저장하는 데 쓸 이차원 배열을 동적으로 생성하기 위한 vector, 파일 입출력을 위한 fstream 라이브러리를 include 해온다.

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

*std 네임스페이스를 미리 선언했다. 이렇게 되면 원래는 std::fstream 형인 fstream을 그냥 fstream으로 사용할 수 있다.

2. 변수들과 파일 스트림 객체를 만들어 준다.

파일 스트림 객체는 fstream 말고도 쓰기만을 위한 ofstream, 읽기만을 위한 ifstream으로도 객체를 생성할 수 있다.

int main(){
    int n;
    int V;
    vector<vector<int>> graph;
    vector<int> visited;
    
    fstream fs;
}

여기서는 굳이 ofstream과 ifstream을 구분하진 않겠다.

3. open()메소드를 이용해 파일을 읽어와 그래프에 저장한다.

int main(){
    int n;
    int V;
    vector<vector<int>> graph;
    vector<int> visited;

    // inputs
    fstream fs;
    fs.open("./test.txt", ios::in);	// 여기서 텍스트 파일 경로 지정
    if(!fs){    // if fails			읽기 실패시 Error 출력
        cerr << "Error!\n";
    }
    fs >> n;						// 형식이 정해져 있을 경우, >> 연산자를 사용 가능하다.
    for(int i = 0; !fs.eof(); i++){
        fs >> V;
        graph.push_back({});
        for(int j = 0; j < V; j++){
            graph[i].push_back(0);
            fs >> graph[i][j];
        }
    }
    fs.close();						// 파일 스트림 닫아주기


    // output - 그래프 정보 출력
    cout << "Graph info - \n";
    for(int i = 0; i < n; i++){
        cout << "Vertex " << i+1 << " - ";
        for(int j = 0; j < graph[i].size(); j++){
            cout << graph[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

- 입력 파일 및 출력 결과

첫 번째 줄에는 그래프 정점의 개수 V가

두 번째 줄~ V+1번째 줄에는 연결된 정점의 개수와 정점의 번호가 입력된다.

4. 전체 코드

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;


int main(){
    int n;
    int V;
    vector<vector<int>> graph;
    vector<int> visited;

    // inputs
    fstream fs;
    fs.open("./test.txt", ios::in);
    if(!fs){    // if fails
        cerr << "Error!\n";
    }
    fs >> n;
    for(int i = 0; !fs.eof(); i++){
        fs >> V;
        graph.push_back({});
        for(int j = 0; j < V; j++){
            graph[i].push_back(0);
            fs >> graph[i][j];
        }
    }
    fs.close();


    // output
    cout << "Graph info - \n";
    for(int i = 0; i < n; i++){
        cout << "Vertex " << i+1 << " - ";
        for(int j = 0; j < graph[i].size(); j++){
            cout << graph[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

1. 변수 한 개를 추가로 생성한다.

void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}

2. xor 연산을 사용한다.

void swap(int *a, int *b){
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
    return;
}

3. 덧셈 연산을 사용한다.

void swap(int *a, int *b){
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
    return;
}

// 또는 더 간단하게
void swap(int *a, int *b){
    *a += *b;
    *b = *a - *b;
    *a -= *b;
    return;
}

1. 방법은 간편하지만 추가로 변수를 생성해야 한다는 단점이 존재하고 (메모리 관점에서 손해)
2. 방법과 3. 방법은 변수를 생성할 필요가 없지만, 사람이 직관적으로 이해하기에는 다소 무리가 있다는 단점이 있다. (가독성 측면에서 손해)
하지만 2. 방법에서는 xor이라는 생소한 개념을 사용하는 반면, 3. 에서는 우리에게 익숙한 + 연산을 사용하므로 구현하기에 무리가 없다.

c++에서 독립적인 함수를 만든다는 가정하에 void형 반환 타입과 포인터 변수를 사용했다.

만약 독립적인 함수가 아닌 다른 함수 내부에서 구현한다고 하더라도, 다음과 같이 a와 b 자리에 값을 바꾸고자 하는 변수를 위치시키면 된다.

** 주의

PS를 할 때 C++에서 list 자료형은 인덱싱을 할 수 없다는 치명적인 결함 때문에 거의 쓰이지 않습니다.

이 글에서는 list 자료형을 사용할 수 있는 방법을 소개했지만, PS를 할 때는 다른 라이브러리를 사용하는 것을 추천드립니다.

1. 개요

알고리즘을 풀 때 만약 요소를 순서대로 조회하면서 인덱싱을 하려면

std::vector 라이브러리나 std::deque, std::map (포인터로 iterator 생성가능) 등의 자료형을 사용할 것이다.

하지만 만약 시퀀스 중간에서 삽입, 삭제가 일어나야 할 경우, 위에 나온 자료형 모두 사용하기가 애매해진다. (map은 확인 필요)

- 특히, std::vector는 push_back, pop_back 등의 메소드는 amortized O(1)로 O(n)이 나올 상황을 방지할 수 없고, 무엇보다 erase() 메소드는 O(n)의 시간복잡도를 가진다.

그래서 인덱싱 및 중간에서의 삽입, 삭제를 O(1)만에 하기 위해서는 list 자료형이 그 무엇보다 간절해진다.

이 글에서는 빠르게 std::list의 사용법, 시간복잡도를 알아보겠다.

2. 사용법

// 예제코드
// Test Source.
#include <list>
using namespace std;

int main() {
	list<int> lst;
	
	return 0;
}

다음과 같이 코드를 짜면 list 자료형을 가지는 lst가 생성된다.

이때 list에서 사용할 수 있는 메소드는 다음 블로그에 잘 정리되어 있으니 참고하기 바란다.

https://losskatsu.github.io/programming/c-stl-list/

3. 인덱싱

하지만 std::list 라이브러리의 가장 큰 문제가 아직 남아있다.

.at()메소드나 인덱싱이 되지 않아 어떤 한 요소에 바로 접근할 수 없는 것이다.

하지만 다음 블로그의 내용을 참고하면 이를 해결할 수 있다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cksdn788&logNo=220448923269 

advance()메소드를 사용하는 것인데 예제 코드는 다음과 같다.

// Test Source.
#include <iostream>
#include <list>
using namespace std;

int main() {	
	list<int> lst;
	list<int>::iterator itr = lst.begin();
	
	for(int i = 0; i < 5; i++)
		lst.push_back(i);
	// test output
	for (itr = lst.begin(); itr != lst.end(); itr++)
		cout << *itr << " ";
	// itr initalize
	itr = lst.begin();
    // itr에 다음 요소의 주소를 할당 (뒤의 숫자만큼 인덱스 증가)
	advance(itr, 1);
	cout << *itr;		

	return 0;
}

- advande(std::list<자료형>::iterator itr, int increaseIdx)

- 뒤의 숫자만큼 다음 인덱스로 가며, 배열의 끝 +1 번지에 도착하는 건 괜찮지만, 그 주소에서 역참조를 해 값을 출력, 연산하려고 하면 오류가 나니 조심하자.

- 이를 이용하면 인덱싱도 가능해진다. (itr = begin()으로 초기화해줘야 함)

무엇보다 advance는 itr에 주소를 할당시켜 주므로 erase()메소드 등을 이용하기 오히려 편리하다.

- 주소를 증가시킨다는 것은 이런  뜻이다.

- i로 실수로 할당하면 포인터가 배열을 벗어난 주소를 가리키게 되니 주의하자.

+)

- 이런 식으로 미리 초기화를 해주면 인덱싱하는것 처럼 쓸 수 있으니 참고하자.

참고한 블로그 : 

https://www.delftstack.com/ko/howto/cpp/how-to-convert-int-to-string-in-cpp/

https://godog.tistory.com/entry/C-string-to-int-int-to-string-%ED%98%95%EB%B3%80%ED%99%98-%ED%95%98%EA%B8%B0

https://velog.io/@dkssk2140/C-%EC%88%AB%EC%9E%90%ED%98%95%ED%83%9C%EC%9D%98-char%EB%A5%BC-int%EB%A1%9C-%ED%98%95%EB%B3%80%ED%99%98

1. int -> string으로 변환하는 방법

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	int i;
	cin >> n;
	string number = to_string(n);
	for (i = 0; i < number.length(); i++)
		cout << number[i];
	return 0;
}

1. string 헤더 include
2. to_string 메서드를 이용해 string 포인터에 전달 (to_string 함수는 string 객체를 반환)

* 단, 부동소수점 리터럴을 to_string 함수에 전달 시 값이 잘리는 문제 발생 가능

- 사용 예시 >

결과 >

앞의 0은 잘리고 나머지 1234만 출력되는 모습을 볼 수 있다.

2. string -> int로 변환 방법

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	int i;
	cin >> n;
	string number = to_string(n);
	n = stoi(number);
	cout << n;

	return 0;
}

마찬가지로, string 헤더를 include 해주고

stoi 함수를 사용해준다. (string to int를 줄인 것)

3. 그럼 char -> int는?

char형을 int로 변환해주면, 일단 c++에서는 문자열은 string형을 쓰기 때문에 char을 int로 바꾼다는 건 보통 한 글자 내에서 연산이 이루어진다는 것이다.

따라서 char형을 int형에 저장하면 그 문자의 아스키코드값 ('1' -> 49)이 나오게 되는데, 여기서 그냥 '1'을 빼고 1을 더해 주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	int i;
	cin >> n;
	string number = to_string(n);
	n = number[0] - '1' + 1;
	cout << n;
	return 0;
}