[알고리즘] 방향 배열 (Direction Array)

알고리즘 기법 중 하나인 방향 배열에 대해 정리한 글입니다.

---

방향 배열 (Direction Array)

• 2차원 이상의 격자 혹은 좌표 공간에서 인접 위치로 이동해야 할 때 각 방향을 일정한 규칙으로 정의해두는 배열
• 2차원 이상의 격자 문제에서 인접 위치로의 접근을 단순화하여 가독성, 유지보수성, 구현 효율을 높여주는 기법
• 보통 BFS/DFS, 시뮬레이션, 그래프 탐색 등에서 빈번하게 사용
• 정식 알고리즘이라기 보다는 반복적인 코드 패턴을 단순화하고 명시화하는 테크닉에 가깝지만, 문제 해결 과정에서 거의 필수적으로 사용될 만큼 유용성이 매우 큰 기법

int dx[4] = { -1, 1, 0, 0 };  // 행(세로) 방향 이동
int dy[4] = { 0, 0, -1, 1 };  // 열(가로) 방향 이동

for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    // (nx, ny)가 격자 범위 안에 있는지, 이동 가능한지 등을 확인한 뒤 처리
}

• 일반적으로 dy, dx라는 배열을 활용하여 이동할 수 있는 방향의 좌표를 정의해두는 방식으로 사용
• 상, 하, 좌, 우 등 이동에 대한 조건문을 따로 처리할 필요 없이 하나의 반복문으로 현재 좌표 (y, x)에서 원하는 모든 방향의 탐색이 가능

---

방향 배열의 일반화

2차원 격자에서의 활용

상하좌우 이동

• for (int i = 0; i < 4; i++)의 반복문 하나로 상하좌우 4방향 탐색 가능
  • dy[4] = {-1, 1, 0, 0}
  • dx[4] = {0, 0, -1, 1}

8방향 이동 (대각선 포함)

• for (int i = 0; i < 8; i++)의 반복문 하나로 상하좌우와 대각선을 모두 포함하여 8방향 탐색 가능
  • dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0}
  • dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1}

말의 이동 (ex. 체스의 나이트)

• 체스의 나이트와 같은 일정한 규칙을 가지고 이동하는 경우, 방향 배열을 이용하여 일반화가 가능
  • dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2}
  • dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1}

다차원으로 확장

• 3차원 문제의 경우, dx, dy, dz 모두 고려가 가능
  • dx[6] = {1, -1, 0, 0, 0, 0}
  • dy[6] = {0, 0, 1, -1, 0, 0}
  • dz[6] = {0, 0, 0, 0, 1, -1}

---

주의 사항

1. 격차 범위 초과 방지
   • 새로운 좌표 (ny, nx)가 문제에서 주어진 범위를 벗어나지는 않는지 매번 검사가 필요
   • 방문 처리(visited 배열 등)를 적절히 활용해야 불필요한 중복 탐색 방지 가능
2. 규칙에 맞는 방향 배열 설정
   • 문제에서 대각선 이동이 가능한지, 특정 예외 조건은 없는지 등을 확인하고 배열 조정이 필요
   • 이동 규칙이 복잡하면, 방향 배열도 길어질 수 있으므로 주석 등을 통해 명확하게 명시
3. 시간 복잡도 측면
   • BFS/DFS에서 이웃 노드를 확인하는 과정은 보통 $ O(1) $ 이며, 전체적으로 모든 노드를 최대 한 번씩 방문한다면, 일반적으로 $ O(N \times M) $ 정도가 됨
   • 방향 배열 자체가 알고리즘의 복잡도를 증가시키는 것은 아니며, 구현을 간소화 하기 위한 역할이 큼
4. 코드 가독성
   1. dx, dy를 전역 혹은 함수 내부에 상수로 정의하면 가독성과 유지보수 측면에서 효율이 좋아짐
   2. 좌표의 순서가 (y, x)인지 (x, y)인지 통일하고 코드를 작성해야 혼동을 방지할 수 있음