JS 알고리즘 - 2차원 탐색 상하좌우

오늘 아래와 같은 2차원 배열 탐색 문제를 푸는데 너무 어려웠다.

문제는 이러하다.

문제

봉우리
지도 정보가 N*N 격자판에 주어집니다.
각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다.
봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.

격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.
0 0 0 0 0 0 0
0 5 3 7 2 3 0
0 3 7 1 6 1 0
0 7 2 5 3 4 0
0 4 3 6 4 1 0
0 8 7 3 5 2 0
0 0 0 0 0 0 0

▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.
▣ 출력설명
봉우리의 개수를 출력하세요.
▣ 입력예제 1
5
5 3 7 2 3
3 7 1 6 1
7 2 5 3 4
4 3 6 4 1
8 7 3 5 2
▣ 출력예제 1
10

 

 

문제 해답

이에 대한 해답을 먼저 보자면 아래와 같다.

  function solution(arr) {
            let answer = 0;
            let n = arr.length;
            let dx = [-1, 0, 1, 0];
            let dy = [0, 1, 0, -1];
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    let flag = 1;
                    for (let k = 0; k < 4; k++) {
                        let nx = i + dx[k];
                        let ny = j + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
                            flag = 0;
                            break;
                        }
                    }
                    if (flag == 1) answer++
                }
            }
            return answer;
        }

 

 

문제 해설

여기서 dx, dy의 역할에 대해 숙지하고 이와 같은 문제가 있을 때마다 응용해야 할 필요성을 느꼈다.

dx와 dy는 방향성을 표현하는 배열이다. 이를 이용해 주어진 좌표의 상하좌우 방향의 인접 좌표를 쉽게 구할 수 있다.
먼저 dx와 dy를 이해하기 위해 아래의 좌표 체계를 이해할 필요가 있다.

(-1,0): 위
(0,1): 오른쪽
(1,0): 아래
(0,-1): 왼쪽

위의 좌표 체계를 토대로 dx와 dy를 보면 dx와 dy는 다음과 같은 방향을 표현한다.

dx[0], dy[0]는 위 방향
dx[1], dy[1]는 오른쪽 방향
dx[2], dy[2]는 아래 방향
dx[3], dy[3]는 왼쪽 방향

 

이것이 코드에서 아래처럼 표현된다. 아래 반복문에서 'k'는 0부터 3까지 4번 반복한다. 

각 k 값에 따라 nx, ny는 현재 위치 (i, j)의 상하좌우 방향의 좌표를 나타낸다.

이를 이용해 arr[nx][ny]로 현재 위치의 상하좌우 방향의 값에 접근할 수 있다.

for (let k = 0; k < 4; k++) {
    let nx = i + dx[k];
    let ny = j + dy[k];
    ...
}