지금까지 이런 탐색법은 없었다 : 델타 배열💣

밍갱·2025년 3월 10일

1. 주제 선정 이유📖

01. 프로그래머스 입문 - 안전지대

오랜만에 프로그래머스 입문 문제를 풀었다. 확실히 입문 문제 90% 이상 넘어가니 난이도가 확 올라가더라(그냥 내가 못하는거임)

02. 그래서 여기서 뭐 어떻게 하라구요...?

일단 지뢰의 위치들을 mines 배열에 넣어주었다. 그리고 이제 그 좌표를 중심으로 주변 8칸에 표시만 해주면 되는데, 여기서 뇌정지가 왔다.

'어떻게 주변 8칸을 구하지?🤔'라는 막막함에 프로그래머스 질문 목록도 찾아보고, 구글링도 해본 결과... 델타 배열이라는 유용한 계산법이 있는게 아닌가! 앞으로 알고리즘에서 2차원 배열과 관련된 문제가 많이 나올 것 같은데, 이참에 한번 정리해보고자 한다. (나중에 두고두고 봐야지)

2. 델타 배열🏁

01. 델타 배열이란?

델타 배열은 2차원 배열([ [],[] ... ])에서 특정 위치의 이동을 쉽게 처리하기 위한 배열로, 특히 8방향(상하좌우+대각선)을 탐색할 때 유용하다. 즉, 2차원 배열에서 특정 위치에서 여러 방향을 탐색할 때, if문을 여러 개 쓰는 것보다 반복문 하나로 해결할 수 있도록 해주는 것이 델타 배열이다.

02. 델타 배열의 구성요소

델타 배열 : 이동할 방향을 정의한 배열

const directions = [
    [-1, 0], [1, 0],  // 상, 하
    [0, -1], [0, 1],  // 좌, 우
    [-1, -1], [-1, 1], [1, -1], [1, 1] // 대각선 (좌상, 우상, 좌하, 우하)
];

델타 배열을 활용한 이동 코드 : 반복문 하나로 여러 방향을 탐색할 수 있다. 기본적인 사용법은 현재 좌표 x, y에서 이동 거리 dx, dy를 더해서 이동

//8방향 탐색
for (let [dx, dy] of directions) {
    let nx = x + dx;  // 새로운 행 위치
    let ny = y + dy;  // 새로운 열 위치

    // 범위 체크 (배열 인덱스 벗어나지 않도록)
    if (nx >= 0 && nx < board.length && ny >= 0 && ny < board.length) {
        console.log(`이동 가능: (${nx}, ${ny})`);
    }
}

범위 체크 : 배열을 탐색할 때 범위를 벗어나면 오류가 발생할 수 있으므로 범위를 체크해줘야한다.

if (nx >= 0 && nx < board.length && ny >= 0 && ny < board.length) {
    // 유효한 좌표일 때만 작업 수행
}

03. 직접 구현 vs 델타 배열

8방향 탐색 직접 구현
각 방향을 하나씩 조건문으로 처리해야 하기 때문에 실수할 가능성 증가하며, 중복된 코드가 많아서 유지보수가 어렵다. 그리고 방향을 추가하면 코드 길이가 늘어난다.

for (let x = 0; x < n; x++) {
    for (let y = 0; y < n; y++) {
        if (board[x][y] === 1) {  // 지뢰 발견
            // 상
            if (x > 0) board[x - 1][y] = -1;
            // 하
            if (x < n - 1) board[x + 1][y] = -1;
            // 좌
            if (y > 0) board[x][y - 1] = -1;
            // 우
            if (y < n - 1) board[x][y + 1] = -1;
            // 좌상
            if (x > 0 && y > 0) board[x - 1][y - 1] = -1;
            // 우상
            if (x > 0 && y < n - 1) board[x - 1][y + 1] = -1;
            // 좌하
            if (x < n - 1 && y > 0) board[x + 1][y - 1] = -1;
            // 우하
            if (x < n - 1 && y < n - 1) board[x + 1][y + 1] = -1;
        }
    }
}

델타 배열을 활용한 8방향 탐색
모든 방향을 for문 하나로 탐색 가능하기 때문에, 코드가 훨씬 짧고 간결해진다. 또한 방향을 추가하거나 수정할 때 쉽게 수정할 수 있다.

//델타 배열 정의
const directions = [
    [-1, 0], [1, 0], [0, -1], [0, 1],  // 상, 하, 좌, 우
    [-1, -1], [-1, 1], [1, -1], [1, 1] // 좌상, 우상, 좌하, 우하 (대각선)
];

for (let x = 0; x < n; x++) {
    for (let y = 0; y < n; y++) {
        if (board[x][y] === 1) {  // 지뢰 발견
            for (let [dx, dy] of directions) {  // 8방향 탐색
                let nx = x + dx;
                let ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 0) {
                    board[nx][ny] = -1;  // 위험지역 표시
                }
            }
        }
    }
}