Matriks adalah struktur data utama untuk grafik komputer, pemrosesan citra, dan aljabar linier. Empat operasi klasik yang sering muncul di soal DSA adalah transpose, perkalian matriks, rotasi 90 derajat, dan spiral traversal. Pada Chapter ini kita akan membedah masing-masing operasi, mulai dari mekanisme permutasi indeks hingga implementasi C++ dengan std::vector<std::vector<int>>. Pemahaman operasi-operasi ini menjadi bekal untuk topik lanjutan seperti transformasi graf dan kompresi citra.

Transpose Matriks #

Mekanisme: Pertukarkan Baris dan Kolom #

Transpose matriks m × n menghasilkan matriks n × m di mana elemen m[i][j] berpindah ke posisi t[j][i]. Untuk matriks persegi (n × n), transpose dapat dilakukan in-place dengan menukar elemen di atas dan di bawah diagonal utama.

Kode: Transpose In-Place (Persegi) #

cpp 
#include <iostream>
#include <vector>

void transpose_square(std::vector<std::vector<int>>& m) {
    int n = static_cast<int>(m.size());
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            std::swap(m[i][j], m[j][i]);
        }
    }
}

void cetak(const std::vector<std::vector<int>>& m) {
    for (const auto& row : m) {
        for (int x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::vector<std::vector<int>> m = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    std::cout << "sebelum:\n"; cetak(m);
    transpose_square(m);
    std::cout << "sesudah transpose:\n"; cetak(m);
    return 0;
}

Output yang Dihasilkan:

text 
sebelum:
1 2 3
4 5 6
7 8 9
sesudah transpose:
1 4 7
2 5 8
3 6 9
  1. Baris for (int j = i + 1; j < n; ++j): loop dalam hanya menjelajah elemen di atas diagonal utama (j > i). Bila kita menjelajah seluruh pasangan (i, j), setiap pasangan akan ditukar dua kali — hasil akhir matriks kembali seperti semula.
  2. Baris std::swap(m[i][j], m[j][i]): menukar elemen simetris terhadap diagonal. Kompleksitas O(1) per pasangan; total O(n²).
  3. Catatan: untuk matriks non-persegi (m × n dengan m ≠ n), transpose tidak bisa in-place — perlu matriks baru berukuran n × m.

Kode: Transpose dengan Ruang Tambahan (Non-Persegi) #

cpp 
#include <iostream>
#include <vector>

std::vector<std::vector<int>> transpose(const std::vector<std::vector<int>>& m) {
    int r = static_cast<int>(m.size());
    int c = static_cast<int>(m[0].size());
    std::vector<std::vector<int>> t(c, std::vector<int>(r));
    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
            t[j][i] = m[i][j];
    return t;
}

void cetak(const std::vector<std::vector<int>>& m) {
    for (const auto& row : m) {
        for (int x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::vector<std::vector<int>> m = {
        {1, 2, 3, 4},
        {5, 6, 7, 8}
    };  // 2x4
    auto t = transpose(m);   // 4x2
    std::cout << "sebelum (2x4):\n"; cetak(m);
    std::cout << "sesudah transpose (4x2):\n"; cetak(t);
    return 0;
}

Output yang Dihasilkan:

text 
sebelum (2x4):
1 2 3 4
5 6 7 8
sesudah transpose (4x2):
1 5
2 6
3 7
4 8
  1. Baris std::vector<std::vector<int>> t(c, std::vector<int>(r));: matriks hasil berukuran c × r — dimensi ditukar.
  2. Baris t[j][i] = m[i][j];: pemetaan indeks transpose. Loop ganda mengunjungi setiap elemen m tepat sekali — kompleksitas O(r * c).

Perkalian Matriks #

Mekanisme: Dot Product Baris-Kolom #

Perkalian matriks A (m × k) dengan B (k × n) menghasilkan matriks C (m × n) di mana:

text 
C[i][j] = sum_{p=0..k-1} A[i][p] * B[p][j]

Syarat: jumlah kolom A harus sama dengan jumlah baris B. Kompleksitas naif: O(m · k · n) — untuk matriks persegi n × n menjadi O(n³).

Kode: Perkalian Matriks Naif #

cpp 
#include <iostream>
#include <vector>

std::vector<std::vector<int>> multiply(
    const std::vector<std::vector<int>>& A,
    const std::vector<std::vector<int>>& B)
{
    int m = static_cast<int>(A.size());
    int k = static_cast<int>(A[0].size());
    int n = static_cast<int>(B[0].size());

    std::vector<std::vector<int>> C(m, std::vector<int>(n, 0));
    for (int i = 0; i < m; ++i) {
        for (int p = 0; p < k; ++p) {
            int a = A[i][p];
            if (a == 0) continue;        // optimasi: skip nol
            for (int j = 0; j < n; ++j) {
                C[i][j] += a * B[p][j];
            }
        }
    }
    return C;
}

void cetak(const std::vector<std::vector<int>>& m) {
    for (const auto& row : m) {
        for (int x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::vector<std::vector<int>> A = {
        {1, 2},
        {3, 4}
    };
    std::vector<std::vector<int>> B = {
        {5, 6},
        {7, 8}
    };
    auto C = multiply(A, B);
    std::cout << "A * B =\n"; cetak(C);
    return 0;
}

Output yang Dihasilkan:

text 
A * B =
19 22
43 50
  1. Baris for (int i...) for (int p...) for (int j...): urutan loop i, p, j dipilih agar akses B[p][j] sekuensial pada j — cache-friendly. Loop p di tengah memungkinkan optimasi skip-nol.
  2. Baris if (a == 0) continue;: bila A[i][p] == 0, kontribusi ke seluruh C[i][*] adalah nol — skip seluruh loop j. Berguna untuk matriks sparse.
  3. Hasil: perkalian [[1,2],[3,4]] * [[5,6],[7,8]] = [[1*5+2*7, 1*6+2*8],[3*5+4*7, 3*6+4*8]] = [[19,22],[43,50]].

Rotasi 90 Derajat #

Mekanisme: Transpose + Reverse #

Rotasi 90 derajat searah jarum jam pada matriks persegi dapat dilakukan dalam dua tahap: transpose lalu reverse setiap baris. Rotasi berlawanan arah: transpose lalu reverse setiap kolom.

Kode: Rotasi 90° Searah Jarum Jam #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>

void rotate90_cw(std::vector<std::vector<int>>& m) {
    int n = static_cast<int>(m.size());
    // Tahap 1: transpose in-place
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            std::swap(m[i][j], m[j][i]);
    // Tahap 2: reverse setiap baris
    for (auto& row : m)
        std::reverse(row.begin(), row.end());
}

void cetak(const std::vector<std::vector<int>>& m) {
    for (const auto& row : m) {
        for (int x : row) std::cout << x << ' ';
        std::cout << '\n';
    }
}

int main() {
    std::vector<std::vector<int>> m = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    std::cout << "sebelum:\n"; cetak(m);
    rotate90_cw(m);
    std::cout << "sesudah rotasi 90 CW:\n"; cetak(m);
    return 0;
}

Output yang Dihasilkan:

text 
sebelum:
1 2 3
4 5 6
7 8 9
sesudah rotasi 90 CW:
7 4 1
8 5 2
9 6 3
  1. Tahap 1 (transpose): sama dengan transpose in-place — menukar elemen di atas diagonal.
  2. Tahap 2 (std::reverse(row.begin(), row.end())): membalik setiap baris. Kombinasi transpose + reverse menghasilkan rotasi 90° searah jarum jam.
  3. Kompleksitas: O(n²) — sama dengan transpose, karena reverse per baris berbiaya O(n) dan dilakukan n kali.

Spiral Traversal #

Mekanisme: Empat Penjuru #

Traversal spiral mengunjungi elemen dari luar ke dalam: kanan → bawah → kiri → atas, lalu ulang untuk lapisan dalam. Setiap lapisan dibatasi oleh empat indeks: top, bottom, left, right.

Kode: Spiral Order #

cpp 
#include <iostream>
#include <vector>

std::vector<int> spiral_order(const std::vector<std::vector<int>>& m) {
    std::vector<int> result;
    if (m.empty()) return result;

    int top = 0, bottom = static_cast<int>(m.size()) - 1;
    int left = 0, right = static_cast<int>(m[0].size()) - 1;

    while (top <= bottom && left <= right) {
        // Kanan: traverse baris top
        for (int j = left; j <= right; ++j) result.push_back(m[top][j]);
        ++top;
        // Bawah: traverse kolom right
        for (int i = top; i <= bottom; ++i) result.push_back(m[i][right]);
        --right;
        // Kiri: traverse baris bottom (jika masih valid)
        if (top <= bottom) {
            for (int j = right; j >= left; --j) result.push_back(m[bottom][j]);
            --bottom;
        }
        // Atas: traverse kolom left (jika masih valid)
        if (left <= right) {
            for (int i = bottom; i >= top; --i) result.push_back(m[i][left]);
            ++left;
        }
    }
    return result;
}

int main() {
    std::vector<std::vector<int>> m = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    auto order = spiral_order(m);
    std::cout << "spiral order:";
    for (int x : order) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
spiral order: 1 2 3 6 9 8 7 4 5
  1. Baris int top, bottom, left, right;: empat pointer yang membatasi lapisan aktif. Setiap iterasi while memproses satu lapisan.
  2. Loop “Kanan”: traverse baris top dari kolom left ke right. Setelah itu, baris atas selesai — geser top ke bawah.
  3. Loop “Bawah”: traverse kolom right dari baris top ke bottom. Setelah itu, kolom kanan selesai — geser right ke kiri.
  4. Cek if (top <= bottom) sebelum loop “Kiri”: bila top > bottom, matriks sudah habis secara vertikal — loop “Kiri” akan menambah elemen ganda. Cegah dengan kondisi.
  5. Hasil: urutan luar 1,2,3,6,9,8,7,4 lalu elemen tengah 5.

Ringkasan #

  • Transpose matriks menukar m[i][j] ↔ m[j][i]. In-place hanya untuk matriks persegi; non-persegi butuh matriks baru.
  • Perkalian matriks naif O(n³); urutan loop i, p, j memberi kinerja lebih baik daripada i, j, p karena cache-friendly.
  • Rotasi 90° searah jarum jam = transpose + reverse tiap baris. Rotasi berlawanan = transpose + reverse tiap kolom.
  • Spiral traversal menggunakan empat pointer (top, bottom, left, right) yang menyusut setiap iterasi while.
  • Semua operasi di atas berbiaya O(n²) untuk matriks persegi — setara dengan jumlah elemen.