2차원 배열 탐색: 행·열·대각선과 상하좌우 경계

2차원 배열의 행·열 합과 상하좌우 이웃은 어떤 좌표 규칙으로 탐색하나요?

2차원 배열에서는 행 r과 열 c를 따로 움직입니다. 행·열의 합을 구할 때와 이웃 네 칸을 비교할 때 사용할 좌표 규칙을 구분하면 됩니다.

[[1,2,3],[4,5,6],[7,8,9]]의 마지막 행 합은 7+8+9=24입니다. 가운데 칸의 상하좌우 값은 2, 8, 4, 6입니다.

적용 조건·범위: [[5]]는 바깥의 0 네 개보다 높아 봉우리 한 개입니다. 같은 높이가 붙어 있으면 엄격히 더 높다는 조건을 만족하지 못합니다. 직사각형 이웃 탐색에는 rows와 cols를 따로 쓰지만, 앞의 두 대각선 합 함수는 N×N 정사각형만 받습니다.

본문 근거: Competitive Programmer’s Handbook — Antti Laaksonen

이 글에서 할 일: 행·열·대각선과 네 방향 이웃의 좌표를 안전하게 계산합니다. 선수 지식: 배열 인덱스·중첩 반복문.

행·열·두 대각선을 따로 더합니다

JavaScript 예제: 격자의 각 행·열·두 대각선의 합을 비교해 가장 큰 값을 구합니다. 아래 코드와 실행 결과, 좌표 표를 함께 보며 각 합이 어떻게 계산되는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function maxLineSum(grid) {
  // 계약: 비어 있지 않은 N × N 숫자 격자
  const n = grid.length;
  let best = -Infinity;
  let main = 0;
  let anti = 0;
  for (let i = 0; i < n; i++) {
    let row = 0;
    let column = 0;
    for (let j = 0; j < n; j++) {
      row += grid[i][j];
      column += grid[j][i];
    }
    best = Math.max(best, row, column);
    main += grid[i][i];
    anti += grid[i][n - 1 - i];
  }
  return Math.max(best, main, anti);
}

console.log(maxLineSum([[1, 2, 3], [4, 5, 6], [7, 8, 9]]));

실행 결과

24

한 행·열을 마치면 두 합과 지금까지의 최댓값을 비교합니다. 대각선은 각 행마다 해당 칸 하나씩 더합니다. 두 대각선의 가운데 칸은 각각의 선에 속하므로 각 대각선 합에 한 번씩 들어갑니다. 모든 선의 합을 한데 더하는 문제가 아닙니다.

node --version

node grid-lines.js

이웃 좌표를 만든 뒤 범위를 확인합니다

JavaScript 예제: 각 칸을 상하좌우 이웃과 비교해 봉우리의 개수를 구합니다. 아래 코드와 두 실행 결과를 보며 격자 안팎의 값을 어떻게 비교하는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function countPeaks(grid) {
  // 계약: 비어 있지 않은 직사각형, 높이는 양수, 바깥 높이는 0
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      let peak = true;
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        const inside = nr >= 0 && nr < rows && nc >= 0 && nc < cols;
        const neighbor = inside ? grid[nr][nc] : 0;
        if (neighbor >= grid[r][c]) { peak = false; break; }
      }
      if (peak) count++;
    }
  }
  return count;
}

console.log(countPeaks([[1, 3, 1], [2, 1, 4]]));
console.log(countPeaks([[5]]));

실행 결과

3
1

현재 칸이 (r,c)라면 위는 (r-1,c), 아래는 (r+1,c), 왼쪽은 (r,c-1), 오른쪽은 (r,c+1)입니다. 값을 읽기 전에 0 ≤ nr < rows와 0 ≤ nc < cols를 모두 확인합니다.

위 봉우리 예제는 양수 높이와 바깥 높이 0을 전제로 합니다. 네 방향 중 같거나 더 높은 칸이 하나라도 있으면 봉우리가 아닙니다. 대각선은 비교하지 않습니다. 배열 테두리에 0을 붙이는 패딩도 가능하지만 바깥 높이의 의미는 문제 조건과 같아야 합니다.

node --version

node peaks.js

한 칸·같은 높이·음수를 구분합니다

[[5]]는 바깥의 0 네 개보다 높아 봉우리 한 개입니다. 같은 높이가 붙어 있으면 엄격히 더 높다는 조건을 만족하지 못합니다. 직사각형 이웃 탐색에는 rows와 cols를 따로 쓰지만, 앞의 두 대각선 합 함수는 N×N 정사각형만 받습니다.

선의 최대합은 음수도 처리하도록 -Infinity에서 시작합니다. 반면 봉우리 예제는 양수 높이 전용입니다. 빈 격자나 들쭉날쭉한 행은 두 함수의 입력 계약 밖입니다.

N×N 선의 합은 O(N²) 시간, R×C 봉우리 탐색은 칸마다 최대 네 번 비교하므로 O(RC) 시간입니다. 이미 주어진 입력과 반환값을 제외한 추가 공간은 두 함수 모두 O(1)입니다.

직접 확인하고 문제에 적용하기

[[2,2],[1,1]]에서 봉우리는 몇 개일까요? [[-5]]의 선 최대합은 얼마일까요?

• 격자판 최대합 풀이
• 봉우리 풀이
• 배열 인덱스와 연산 비용

참고 자료

자료 확인일: 2026년 10월 19일.

• Competitive Programmer’s Handbook — Antti Laaksonen — 7.3절의 격자 좌표와 행·열 표현.