스레드로 돌아가기

leetcode에서 cpp 사용 기초 - vector활용

3 min#ps#leetcode#cpp
class Solution {
public:
    int di[4] = {-1, 0, 1, 0};
    int dj[4] = {0, 1, 0, -1};
    int n, m;
    
    vector<vector<bool>> visited;

    bool containsCycle(vector<vector<char>>& grid) {
        n = grid.size();
        m = grid[0].size();
        visited.assign(n, vector<bool>(m, false)); // Arrays.fill이랑 똑같음

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    if (go(i, j, -1, -1, grid[i][j], grid)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool go(int i, int j, int pi, int pj, char color, vector<vector<char>>& grid) {
        visited[i][j] = true;

        for (int k = 0; k < 4; k++) {
            int ni = i + di[k];
            int nj = j + dj[k];

            if (isValid(ni, nj, color, grid)) {
                // 만약 다음 칸이 이미 방문한 곳인데, 직전 칸이 아니면
                if (visited[ni][nj]) {
                    if (ni != pi || nj != pj) {
                        return true;
                    }
                } else {
                    if (go(ni, nj, i, j, color, grid)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool isValid(int ni, int nj, char c, vector<vector<char>>& grid) {
        return ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == c;
    }
};

vector를 좀 더 잘 활용할 필요가있다.

자바의 ArrayList쓰듯이 해보자.

vector는 뭐냐

vector는 C++ STL에서 제공하는 동적 배열이다.

자바로 치면 ArrayList랑 제일 비슷하다. 크기가 고정된 배열이 아니라, 원소를 뒤에 계속 추가할 수 있고 인덱스로 바로 접근할 수 있다.

#include <vector>
using namespace std;

vector<int> v;
v.push_back(10);
v.push_back(20);

cout << v[0]; // 10
cout << v.size(); // 2

자바로 쓰면 이런 느낌이다.

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);

System.out.println(list.get(0)); // 10
System.out.println(list.size()); // 2

대충 대응시키면 이렇게 보면 된다.

C++ vectorJava ArrayList의미
vector<int> v;ArrayList<Integer> list = new ArrayList<>();빈 리스트 만들기
v.push_back(x);list.add(x);뒤에 원소 추가
v[i]list.get(i)i번째 원소 읽기
v[i] = x;list.set(i, x)i번째 원소 수정
v.size()list.size()크기 확인
v.clear()list.clear()전체 삭제

차이점도 있다. C++의 vector<int>는 int를 그대로 담는다. 자바의 ArrayList<Integer>는 primitive int가 아니라 wrapper인 Integer를 담는다. 그래서 PS에서는 C++ vector<int>가 훨씬 가볍고 자주 쓰인다.

vector 선언 방식

가장 기본은 이거다.

vector<int> arr;

처음부터 크기를 정해서 만들 수도 있다.

vector<int> arr(5);

이러면 크기 5짜리 vector가 만들어지고, int는 기본값인 0으로 채워진다.

// [0, 0, 0, 0, 0]

초기값까지 같이 주고 싶으면 이렇게 한다.

vector<int> arr(5, -1);

자바로 치면 아래랑 비슷하다.

int[] arr = new int[5];
Arrays.fill(arr, -1);

다만 자바의 int[]는 길이가 고정이고, C++의 vector<int>는 뒤에 push_back으로 더 붙일 수 있다.

2차원 vector

위 코드에서는 이 문법이 나온다.

vector<vector<bool>> visited;

처음 보면 꺾쇠가 두 번 나와서 좀 무서운데, 그냥 vector 안에 vector가 들어간 것이다.

자바로 치면 이런 느낌이다.

ArrayList<ArrayList<Boolean>> visited;

그런데 알고리즘 문제에서는 보통 2차원 배열처럼 쓴다.

visited[i][j] = true;

if (visited[i][j]) {
    // 이미 방문함
}

자바의 2차원 배열이랑 비교하면 거의 똑같이 읽으면 된다.

boolean[][] visited = new boolean[n][m];
visited[i][j] = true;

즉 vector<vector<bool>> visited;는 boolean[][] visited;랑 비슷한 역할을 한다.

assign으로 크기와 초기값 정하기

코드에서 제일 중요한 부분은 이거다.

visited.assign(n, vector<bool>(m, false));

뜻은 다음과 같다.

  • visited를 크기 n짜리 vector로 만든다.
  • 각 칸에는 vector<bool>(m, false)를 넣는다.
  • 즉 길이 m짜리 bool vector를 n개 만든다.
  • 결과적으로 n * m 크기의 2차원 방문 배열이 된다.

그림으로 보면 이런 구조다.

visited = [
  [false, false, false],
  [false, false, false],
  [false, false, false]
]

만약 n = 3, m = 3이면 위처럼 된다.

자바로 쓰면 이 느낌이다.

boolean[][] visited = new boolean[n][m];

for (int i = 0; i < n; i++) {
    Arrays.fill(visited[i], false);
}

사실 자바의 boolean[][]은 기본값이 false라서 Arrays.fill을 안 해도 되긴 한다. 그래도 C++의 assign(n, vector<bool>(m, false))를 자바식으로 이해하면 "n행 m열짜리 배열을 만들고 전부 false로 채운다"가 된다.

grid는 왜 &가 붙어있나

함수 파라미터에 이런 코드가 나온다.

bool containsCycle(vector<vector<char>>& grid)

여기서 vector<vector<char>>는 2차원 char 배열이다.

자바로 치면 문제에 따라 이런 것과 비슷하다.

char[][] grid

그런데 C++에는 뒤에 &가 붙어 있다.

vector<vector<char>>& grid

이 &는 참조(reference) 라는 뜻이다. 쉽게 말하면 원본을 그대로 받아온다는 뜻이다.

만약 & 없이 이렇게 쓰면,

bool containsCycle(vector<vector<char>> grid)

함수를 호출할 때 grid 전체가 복사될 수 있다. 2차원 배열이 크면 당연히 느리다.

그래서 알고리즘 문제에서는 보통 이렇게 쓴다.

bool containsCycle(vector<vector<char>>& grid)

자바는 객체를 넘길 때 기본적으로 참조값이 넘어가니까, ArrayList나 배열을 함수에 넘길 때 매번 전체 복사가 일어나지 않는다. C++에서는 복사를 피하려고 &를 직접 붙여주는 느낌으로 이해하면 된다.

그리고 함수 안에서 grid를 수정하지 않을 거라면 더 엄격하게 이렇게도 많이 쓴다.

bool containsCycle(const vector<vector<char>>& grid)

const는 "읽기만 할 거고 수정하지 않겠다"는 뜻이다. 다만 LeetCode의 함수 시그니처가 정해져 있으면 거기에 맞춰야 한다.

size()와 인덱스 접근

위 코드에서는 행과 열 크기를 이렇게 구한다.

n = grid.size();
m = grid[0].size();

grid.size()는 바깥 vector의 크기다. 즉 행의 개수다.

grid[0].size()는 0번째 행의 크기다. 즉 열의 개수다.

자바로 치면 이런 느낌이다.

n = grid.length;
m = grid[0].length;

원소 접근은 []를 두 번 쓰면 된다.

grid[i][j]
visited[i][j]

자바의 2차원 배열 접근이랑 똑같다.

grid[i][j]
visited[i][j]

참고로 C++ vector에는 v.at(i)도 있다.

v.at(i)

at()은 범위를 벗어나면 예외를 던져준다. 대신 PS에서는 보통 속도와 간결함 때문에 v[i]를 많이 쓴다. 범위 체크는 직접 isValid 같은 함수로 해주는 식이다.

이 코드에서도 먼저 범위를 확인하고,

bool isValid(int ni, int nj, char c, vector<vector<char>>& grid) {
    return ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == c;
}

그 다음에 grid[ni][nj]에 접근한다. 이 순서가 중요하다. 범위 밖인데 grid[ni][nj]를 먼저 하면 터진다.

이 코드의 vector 문법 정리

이 코드에서 vector 관련해서 봐야 할 문법은 이 정도다.

vector<vector<bool>> visited;

2차원 bool vector를 멤버 변수로 선언한다. DFS 중에 여러 함수에서 같이 쓰려고 클래스 안에 빼둔 것이다.

bool containsCycle(vector<vector<char>>& grid)

2차원 char vector를 참조로 받는다. 복사를 피하려고 &를 붙인다.

n = grid.size();
m = grid[0].size();

행 개수와 열 개수를 구한다.

visited.assign(n, vector<bool>(m, false));

n행 m열짜리 방문 배열을 만들고 전부 false로 초기화한다.

visited[i][j] = true;
if (visited[ni][nj]) { ... }

2차원 배열처럼 인덱스로 접근한다.

grid[ni][nj] == c

현재 칸의 문자가 내가 찾는 색깔과 같은지 확인한다.

Java에서 C++로 옮길 때 감각

자바에서 이렇게 쓰던 사람이라면,

boolean[][] visited = new boolean[n][m];
char[][] grid;

visited[i][j] = true;
if (grid[ni][nj] == color) {
    ...
}

C++에서는 이렇게 옮기면 된다.

vector<vector<bool>> visited(n, vector<bool>(m, false));
vector<vector<char>> grid;

visited[i][j] = true;
if (grid[ni][nj] == color) {
    ...
}

또 자바의 ArrayList<Integer>처럼 1차원 리스트가 필요하면,

ArrayList<Integer> arr = new ArrayList<>();
arr.add(3);
arr.add(5);

C++에서는 이렇게 쓴다.

vector<int> arr;
arr.push_back(3);
arr.push_back(5);

정리하면, PS에서 vector는 거의 기본 장비다. 1차원 배열, 2차원 배열, 그래프 인접 리스트, 좌표 목록 전부 vector로 만들 수 있다. 자바에서 ArrayList와 배열을 섞어 쓰던 감각을 C++에서는 대부분 vector 하나로 가져갈 수 있다고 보면 된다.