델타 배열을 이용해 2차원 배열 탐색하기

2차원 배열

• "행(row)"과 "열(column)" 두 차원을 가진 배열 (논리적 시점)
• 1차원 배열을 요소로 가지는 배열 (코드 시점)

 2차원 배열을 활용하면, 게임의 보드판(예: 오목판, 체스판), 이미지의 픽셀 정보, 수학에서 다루는 행렬, 다양한 그래프, 표 등과 같이 행과 열로 이루어진 데이터를 손쉽게 처리할 수 있다.

 

출처 : https://www.digitalocean.com/community/tutorials/two-dimensional-array-in-c-plus-plus

 

 

 

델타 배열

 2차원 배열에서 순회/탐색을 돕기 위해 선언한 배열.

        // 4방향 델타 배열(상하좌우)
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        final int d = 4;

        // 8방향 델타 배열 (↑↓←→ ↖↗↙↘)
        int[] dx = {0,0,-1,1,-1,1,-1,1};
        int[] dy = {-1,1,0,0,-1,-1,1,1};
        final int d = 8;

 

사용 예시

 

문제 : 위와 같은 2차원 배열에서, 지정된 한 칸과 상하좌우에 있는 칸의 수의 합이 가장 큰 경우를 찾아서 그 값을 출력하라. 

 

public static int solution(int[][] grid) {

        // 합의 최대값
        int maxSum = 0;

        // 델타 배열 (상하좌우)
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        final int d = 4;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {

                int sum = grid[i][j];                
                
                for (int k = 0; k < d; k++) {
                
                    // 델타 배열 사용
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    // 배열 범위 밖이라면 패스
                    if (nx < 0 || ny < 0 || nx >= grid.length || ny >= grid[i].length) continue;

                    sum += grid[nx][ny];
                }

                maxSum = Math.max(maxSum, sum);
            }
        }

        return maxSum;
    }