[Java] 델타를 이용한 2차원 배열 탐색 (자바 | Java)

[Java] 델타를 이용한 2차원 배열 탐색

---

좌표 이동과 탐색

DFS/BFS 문제를 접하다 보면(기본적인 예로 미로찾기, 그림 등) 좌표의 성질을 갖는 특정 원소에서 다른 원소로의 이동이나, 그 주변(4방, 8방)을 탐색 하는 로직 구현이 자주 사용된다.

2차원 배열에서의 좌표

일반적으로 좌표를 생각한다면, 다음과 같이 수학에서의 1사분면 좌표를 떠올리게 된다.

x의 값이 증가하면 오른쪽으로 이동하고 y의 값이 증가하면 위쪽으로 이동하는 구조이다. 그러나 2차원 배열에서의 좌표를 생각해보면 위와는 달리, y의 값이 증가 할수록 아래로 이동한다. 행렬을 생각해보면 이해하기 더 쉽다.

로직

순회 / 탐색 방향에 따른 계산

한 지점(좌표) P가 8방향을 탐색 할 때의 좌표값 계산이다.

주의해야 할 점은, 순회하는 범위가 배열의 범위를 넘어가면 안된다.
이 포스팅에서는 4방향 탐색을 구현한다.

input

int[][] map = { {1, 2, 3, 4},
                {5, 6, 7, 8},
                {3, -5, 3, 4},
                {5, 5, 3, 2}};

위와 같은 입력이 들어오고, -5를 기준으로 상하좌우 즉, 4방향 원소의 값을 탐색 하는 코드는 다음과 같다.

델타를 이용

public class DeltaSearch {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0}; // 오른쪽 아래 왼쪽 위

    public static void main(String[] args) {
        int N = 4;
        int[][] map = { {1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {3, -5, 3, 4},
                        {5, 5, 3, 2}};

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("타겟의 오른쪽, 아래, 왼쪽, 위 순으로 출력");
        System.out.println("--------------");

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == -5) {
                    System.out.printf("x = %d y = %d\n", j, i);
                    for (int d = 0; d < N; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];

                        if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                            continue;
                        }
                        System.out.println(map[nx][ny]);
                    }
                    System.out.println("--------------");
                }
            }
        }
    }
}

dx, dy 배열의 값을 선언해주고, 2중 for문 안에 4방향 탐색을 위한 for문에서는
다음과 같이 4방향 탐색을 한다.

• d = 0
  dx[0], dy[0] = (0, 1)
• d = 1
  dx[1], dy[1] = (1, 0)
• d = 2
  dx[2], dy[2] = (0, -1)
• d = 3
  dx[3], dy[3] = (-1, 0)

또한

if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                            continue;
                        }

위와 같은 예외문을 통해 유효하지 않은 범위는 예외 처리를 해준다.

output

결과는 다음과 같이 나온다.

--------------
x = 1 y = 2
3 // right
5 // down
3 // left
6 // up
--------------