leetcode에서 cpp 사용 기초 - vector활용
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++ vector | Java 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 하나로 가져갈 수 있다고 보면 된다.