[자료구조] Sparse Matrix 희소행렬

💡 희소행렬(Sparse Matrix)이란?
원소 대부분이 0으로 이루어진 행렬

행렬은 2차원 배열로 구현할 수 있다. 그렇다면 대부분이 0으로 채워진 sparse matrix를 좀 더 의미있는 2차원 배열로 축약할 수는 없을까?
matrix에서 0이 아닌 데이터들을 뽑아내서 밀집 행렬(dense matrix)을 만들어보자.

class Entry {
	int row;	// 행
	int col;	// 열
	int value;	// 담긴 값
	
	public Entry(int row, int col, int value) {
		this.row = row;
		this.col = col;
		this.value = value;
	}
}

public class SparseMatrixTest {
	final static int ARRSIZE = 10;
	final static int MTXSIZE = ARRSIZE * ARRSIZE;
	
	public static void printDenseMTX(Entry[] denseMTX) {
		System.out.println("row\tcol\tvalue");
       		![](https://velog.velcdn.com/images%2Filmerry%2Fpost%2Fbf4e0b54-41ee-4f0e-9ce8-583f8d5e5ba0%2FSparse_Matrix_%ED%9D%AC%EC%86%8C%ED%96%89%EB%A0%AC.png)![](https://velog.velcdn.com/images%2Filmerry%2Fpost%2F9bae4e16-dfdc-4826-b801-8a736384f182%2FSparse_Matrix_%ED%9D%AC%EC%86%8C%ED%96%89%EB%A0%AC.png)// 의미있는 값들의 개수만큼 반복
		for(int i=0; i<denseMTX[0].value; i++) {
			System.out.println(denseMTX[i].row + "\t"
					+ denseMTX[i].col + "\t"
					+ denseMTX[i].value);
		}
	}
	
	public static Entry[] coordinate(int[][] sparseMTX) {
		int position=1;
		Entry[] denseMTX = new Entry[MTXSIZE];
		
		// 행렬관련 정보 저장
		denseMTX[0] = new Entry(ARRSIZE, ARRSIZE, 0);
		
		for(int i=0; i<ARRSIZE; i++) {
			for(int j=0; j<ARRSIZE; j++) {
				if(sparseMTX[i][j] != 0) {
					denseMTX[position] = new Entry(i, j, sparseMTX[i][j]);
					
					position++;
				}
			}
		}
		denseMTX[0].value = position-1;
		
		return denseMTX;
	}

	public static void main(String[] args) {
		int matrix[][] = new int[ARRSIZE][ARRSIZE];
		Entry[] denseMTX = new Entry[MTXSIZE];

		matrix[0][0] = 15;
		matrix[0][2] = 22;
		matrix[0][9] = 15;
		matrix[1][8] = 3;
		matrix[2][1] = 28;
		matrix[3][0] = 91;
		
		denseMTX = coordinate(matrix);
		printDenseMTX(denseMTX);
	}

}

실행결과