SMParkWorld - [C/C++] 다차원 배열 초기화

[C/C++] 다차원 배열 초기화

2021-06-11 15:54:05

Algorithm

오늘은 C++로 알고리즘 문제를 풀 때 다차원 배열을 초기화하는 법에 대해서 적어두려 한다.

먼저 초기화 방법에 따라 나누어진다. 선언과 동시에 초기화하는 법과 선언 후 나중에 함수를 사용해서 초기화하는 방법이 있다. 선언과 동시에 초기화하는 법은 대충 구글링만 해도 자료가 많아서 여기서는 함수를 사용해서 초기화하는 방법에 대해서만 다룰 예정이다.

내가 자주 사용하는 함수는 크게 두가지다. memset() 혹은 fill()함수인데 성능은 fill보다 memset이 더 좋다고 한다. 하지만 사용하는 목적에 따라 다르게 사용되니 상황에 따라 잘 선택하면 될 것 같다.

먼저 memset은 아래와 같이 사용한다.

int main() {
    bool isVisited[15];
    memset(isVisited, 0, sizeof(isVisited));
}

1번째로 초기화할 배열의 시작주소를 전달하고 2번째로 초기화 하려는 값, 3번째로 초기화할 배열의 크기를 전달한다.

하지만 위와 같이 초기화 하려는 값이 1byte이하인 경우는 문제되지 않지만 int와 같은 자료형을 초기화하면 문제가된다. memset은 기본적으로 2번째 아규먼트인 초기화 하려는 값을 1byte로 읽고 초기화하기 때문에 기대한 결과를 얻지 못한다.

그래서 C++에서는 std::fill 함수를 사용하면 된다.

int main() {
    int array[15];
    fill(array, array + 15, 15151515);
}

1번째로 초기화할 배열의 시작주소를 전달하고 2번째로 초기화할 배열의 마지막 주소, 3번째로 초기화 하려는 값을 전달한다.

하지만 다차원 배열의 경우 위와 같이 사용하면 안되고 아래와 같이 사용해야 한다.

int main() {
    int array[15][15];
    fill(&array[0][0], &array[14][15], 15151515);
}

정리하면, memset()함수가 fill() 함수보다 비교적 성능이 좋다고 하니 1byte 이하인 char나 bool 값 등을 초기화할 때는 memset() 함수를 사용하고 그 외의 값들을 초기화할 때는 fill() 함수를 사용하는 것이 좋을 것 같다.

아래는 위와 같이 다차원 배열 초기화를 사용한 알고리즘 문제다. 카카오 인턴십의 경주로 건설 문제이고 프로그래머스에서 풀 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int estimates[25][25];
int mx[4] = { 0, 1, 0, -1 };
int my[4] = { 1, 0, -1, 0 };
 
int solution(vector<vector<int>> board) {
    
    fill(&estimates[0][0], &estimates[24][25], INT_MAX);
    
    queue<vector<int>> q;       // vector == [x, y, direction, straightRoad, corner]
    q.push({1, 0, 1, 1, 0});
    q.push({0, 1, 2, 1, 0});
    estimates[0][0] = 0;
    
    int n = board.size();
    while (!q.empty()) {
        vector<int> p = q.front(); q.pop();
            
        int tmpEstimate = (p[3] * 100) + (p[4] * 500);
        if (board[p[1]][p[0]] || estimates[p[1]][p[0]] < tmpEstimate) continue;
        estimates[p[1]][p[0]] = tmpEstimate;
        
        for (int d = 0; d < 4; d++) {
            int x = p[0] + mx[d];
            int y = p[1] + my[d];
            
            if (y < 0 || x >= n || y >= n || x < 0) continue;
            q.push({x, y, d, p[3] + 1, (p[2] % 2 == d % 2) ? p[4] : p[4] + 1});
        }
    }
    
    return estimates[n - 1][n - 1];
}

11번째 줄에서 fill() 함수를 사용하고 있다. DFS/BFS 문제였고 재방문 처리에 조금 신경쓰면 쉽게 풀 수 있는 문제였다. 아래의 주소에서 해당 문제를 직접 풀 수 있다.