[프로그래머스/C++] Level2 - 게임 맵 최단거리 #vector #pair # tuple # auto #reverse #find #sort #distance

 

오랜만에 C++을 사용해보려고 한다.

익숙해져볼까나,,,

 

뭔가 아주 예전에 C++ 백터 처음 써볼 때는 상당히 낯설었다. 오늘 써보니까 그냥 동적 배열이다. 

게임 맵 최단거리 [ 링크 ]

 

Today I Learned : ]

1. vector 다루기
  - find, sort, reverse, distance
2. auto 개념과 사용하기
3. pair, tuple 다루기
4. 람다와 일급 객체

요약

 

(0,0) 에서 우측 하단 으로 도달할 수 있는 최단 거리 구하기

 

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

vector<pair<int,int>> directions = {{-1,0},{1,0},{0,1}, {0,-1}};
int solution(vector<vector<int> > maps) {
    int height = maps.size();
    int width = maps[0].size();
    vector<tuple<int, int, int>> queue = {{0,0,1}};
    maps[0][0] = 0;
    int idx = 0;

    while (queue.size() > idx) {
        auto [cx, cy, cnt] = queue[idx++];
        if (cy==height-1 && cx==width-1) return cnt;
        for (const auto&[dx, dy] : directions) {
            int nx = dx+cx, ny = dy+cy;
            bool isOutOfBounds = nx<0 || ny<0 || nx>=width || ny>=height;
            if (isOutOfBounds || maps[ny][nx]==0) continue;
            queue.push_back({nx,ny,cnt+1}); // C++ 17부터는 make_tuple 안써도됨
            maps[ny][nx] = 0;
        }
    }
    return -1;
}

 

 

새롭게 알게 된 개념

#vector  #pair  #tuple  #auto  #reverse  #find  #sort  #distance

 

Vector 간단히 알아본 특징

vector는 JS, Swift에서 선언하는 배열과 같다. 클래스 템플릿 이라고 한다. 동적 배열. JS와 다르게,, Swift와 같게 연속적인 메모리에 값들을 주입한다. 

 

접근 방식은 front, back 이나 at 또는 [] 로도 가능하다.

 

 

클래스 템플릿인데,, 

template <class Type, class Allocator = allocator<Type>>
class vector;

 

vector는 Type, Allocator라는 두개의 인자값을 받는다. Allocator 기본 값은 설정되어있어서 vector<int>라고하면 템플릿의 Type은 int가 된다.

 

C++ Vector 요소들은 연속적으로 저장된다. Swift랑 비슷하게 capacity, size개념을 사용한다. 동적 배열에서는 메모리에 얼마나 점유를 해야하는지 런타임에 생각해야 함. 그래서 capacity를 활용한다. 생각보다 많은 데이터가 추가될 경우에 메모리 재할당(reallocation)을 수행한다. 

 

신기한 것은 list 형식의 저장 방식도 지원한다.

 

 

Swift의 제너릭이랑 C++의 템플릿은 의미가 비슷한데 Swift의 제너릭은 컴파일 시점 + 런타임 시점에 동작하는데 C++의 제너릭은 Static Dispatch(컴파일 시점)로 동작한다고 한다. 

---

 

Vector 사용 방법

 

vector's CRUD, sort, reverse를 다루면 좋을것 같다. C++도 일급 객체의 특징을 갖고 있다.

vector의 begin, end 함수는 시작과 끝 위치를 알려주는 포인터(iterator)라고 한다. Range를 지정하기 위함.

이때 end는 마지막 원소 다음 idx를 가리킨다.

sort, reverse, find, distance 같은 함수 쓰기 위함이라고 함.

 

vector<int> seq; // JS: let v1 = [];
vector<string> seq2(3); // 크기 3칸 기본값 ""
vector<int> seq3(3, 100); // 크기 3칸 기본값 100 꽉 채우기
vector<int> seq4 = {10, 20, 30}; // JS: let seq = [10, 20, 30];

// CRUD
seq.push_back(40); // 맨 뒤에 추가
seq.pop_back(); // 맨 뒤에 원소 삭제
seq.clear(); // 원소 전부 삭제
cout<<seq[2]; // 대괄호 접근 가능
seq.at(2); // seq[2]와 같음. 없을 경우 exception 던짐

cout << seq.front(); //맨 앞 원소 접근
cout << seq.back(); // 맨 뒤 원소 접근

 

reverse

#include <algorithm>

/// 뒤집기
vector<int> seq = {10, 20, 30, 40};
reverse(v.begin(), v.end());

for (int e: seq) cout << e << " "; // 40, 30, 20, 10

 

sort와 일급 객체

/// default sort

vector<int> v = {10, 20, 30, 40};

sort(v.begin(), v.end()) // 기본 오름차순 10, 20, 30, 40


/// 여기에 comparator 람다로 지정 가능
sort(v.begin(), v.end(), [](int lhs, int rhs) {
	return lhs > rhs ;
});


/// 근데 타입 추론 귀찮은 경우
sort(v.begin(), v.end(), [](const auto& lhs, const auto& rhs) {
	return lhs > rhs;
});


/// C++ 에서도 First-Class Citizen은 지원한다.
auto comparator = [](const auto& lhs, const auto& rhs) {
	return lhs < rhs;
}
sort(v.begin(), v.end(), comparator);

 

vector 복사

vector<int> v = {10, 20, 30, 40, 50};

// 두 번째 원소부터 ~~ 네 번째 원소까지 복사해서 v2를 만듬
vector<int> v2(v.begin() + 1, v.end() - 1);     // v2는 {20, 30, 40}

 

find, distance

vector <int> v = {10, 20, 30, 40, 50};

/// 20 찾아보자.
auto found = find(v.begin(), v.end(), 20);

/// 못 찾았니?
if (found == v.end()) { // 못찾음 }
else {
	// 값 접근
    cout << *found << endl;
    
    // 인덱스 접근
    int foundIdx = distance(v.begin(), found); // index ==> 1
}

 

References

https://en.cppreference.com/w/cpp/container/vector.html

std::vector - cppreference.com