[Data Structures] 방향 배열 (Direction Array)

2차원 배열이나 그리드 기반의 문제에서 주어진 위치의 4방향(상, 하, 좌, 우) 또는 8방향(상, 하, 좌, 우, 대각선 포함) 으로 이동하기 위한 좌표 값 획득을 위해 사용한다. DFS, BFS, 다익스트라 알고리즘에서 활용할 수 있다.

---

방향 배열 Offset Sample

4방향, 8방향 배열을 만들 때는 행, 열을 기준으로 2개의 Offset을 만들어야 한다.

• 4방향 배열 Offset (상, 하, 좌, 우)

int[] dRow = {-1, 1, 0, 0};  // 행 방향
int[] dCol = {0, 0, -1, 1};  // 열 방향

• 8방향 배열 Offset (상, 하, 좌, 우, 상우, 하우, 하좌, 상좌)

int[] dRow = {-1, 1, 0, 0, -1, 1, 1, -1};  // 행 방향
int[] dCol = {0, 0, -1, 1, 1, 1, -1, -1};  // 열 방향

 

방향 배열 주의사항

• offset 구성 시 방향 값 맵핑 순서를 정확하게 반영해야 한다. 
  ※ 2개의 offset 배열을 만들 때 특정 순번의 인덱스는 서로 같은 방향으로 향하도록 해야 한다.
• 방향 배열을 활용할 때 반복은 방향의 개수만큼 진행해야 한다. (4방향 배열 = 4번, 8방향 배열 = 8번)
• 배열의 인덱스 범위를 벗어나는 지 체크하는 조건문이 항상 들어가야 한다.
• 방향의 우선순위가 주어지는 경우 offset 구성에 신경써야 한다.

 

2차원 배열 주어진 위치에서 상, 하, 좌, 우 좌표의 값을 더하는 예제 코드

• 변수 값 초기화

// 샘플 데이터
int arr[][] = {
    {1, 1, 1}, 
    {1, 0, 1}, 
    {1, 1, 1} 
};

// 4방향 배열 초기화
int[] rowD = {-1, 1, 0, 0};
int[] colD = {0, 0, -1, 1};

• 주어진 위치 값 초기화

int row = 1;
int col = 1;

• 4방향을 순회하며 요소들을 모두 더하는 반복문

int result = 0;
for (int i=0; i<4; i++) {
    int nr = row + rowD[i];
    int nc = col + colD[i];

    result = result + arr[nr][nc];
}

System.out.println(result);

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        int arr[][] = {
            {1, 1, 1}, 
            {1, 0, 1}, 
            {1, 1, 1} 
        };
        
        int[] rowD = {-1, 1, 0, 0};
        int[] colD = {0, 0, -1, 1};

        int row = 1;
        int col = 1;
        int result = 0;
        for (int i=0; i<4; i++) {
            int nr = row + rowD[i];
            int nc = col + colD[i];

            result = result + arr[nr][nc];
        }

        System.out.println(result);

    }
}

 

인덱스 범위를 벗어나는 경우 예외처리 하는 예제 코드

위의 예제에서 주어지는 위치 값으로 [0][0] 인덱스가 주어지면 예제 코드 실행 결과 ArrayIndexOutOfBoundsException이 발생한다. 이런 경우를 대비하기 위해 예외처리 코드가 추가되어야 한다.

• 예외처리 코드

int row = 0;
int col = 0;
int result = 0;
int rowSize = arr.length;		// 배열의 행 크기
int colSize = arr[0].length;	// 배열의 열 크기
for (int i=0; i<4; i++) {
    int nr = row + rowD[i];
    int nc = col + colD[i];
	
    // nr >= rowSize : row 값이 배열의 행 크기 보다 크거나 같은 경우
    // nc >= colSize : col 값이 배열의 열 크기 보다 크거나 같은 경우
    // nr < 0 : row 값이 0보다 작은 경우 (음수)
    // nc < 0 : col 값이 0보다 작은 경우 (음수)
    if (nr >= rowSize || nc >= colSize || nr < 0 || nc < 0) continue;	// 조건건을 충족 하면 다음 반복문으로 넘어간다.

    result = result + arr[nr][nc];
}

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        int arr[][] = {
            {1, 1, 1}, 
            {1, 0, 1}, 
            {1, 1, 1} 
        };

        int[] rowD = {-1, 1, 0, 0};
        int[] colD = {0, 0, -1, 1};

        int row = 0;
        int col = 0;
        int result = 0;
        int rowSize = arr.length;
        int colSize = arr[0].length;
        for (int i=0; i<4; i++) {
            int nr = row + rowD[i];
            int nc = col + colD[i];

            if (nr >= rowSize || nc >= colSize || nr < 0 || nc < 0) continue;

            result = result + arr[nr][nc];
        }

        System.out.println(result);

    }
}