해당 포스팅은 인프런의 "자바스크립트 알고리즘 문제풀이" 강의 중 챕터2의 봉우리 문제 풀이를 다룬다. 스택으로 풀이하였다.
백준의 DFS문제인 Two Dots와 비슷한 문제이다. 저번에 풀려고 시도했다가 실패했는데 다시 한번 도전해봐야지! 🔥🔥🔥
문제
문제 설명
풀이
문제에서 input으로 아래의 2차원 배열이 주어진다.
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해당 2차원 배열을 그림으로 표현하면 아래와 같다. 격자의 가장자리는 0이라고 나와있으므로 2차원 행렬의 가장자리가 0으로 감싸져있다. 원소가 상하좌우의 원소들보다 클 시 봉우리라고 하였으므로, 회색으로 칠해진 원소들이 봉우리가 될 수 있다.
따라서 현재 원소와 해당 원소의 상하좌우의 원소들의 크기를 비교해주면 되는 문제이다.
로직
예제로 주어지는 2차원 배열은 아래 사진과 같다.
그 중 arr[1][2]가 봉우리인지 판별해보자.
위의 사진을 보면 원소의 상하좌우 원소들의 좌표는 다음과 같다.
상 : x = i-1, y = j
하 : x = i+1, y = j
좌 : x = i, y = j-1
우 : x = i, y = j+1
즉 각 원소들의 좌표마다 더해주어야 하는 값이 있다.
상하좌우의 x, y좌표의 값을 판별하기 위해 x,y좌표에 더해주어야 하는 값들을 각 배열로 만들자.
이를 코드로 표현하면 아래와 같다.
const dx=[-1, 0, 1, 0];
const dy=[0, 1, 0, -1];dx, dy 배열을 이용해 현재 원소의 값과 상하좌우의 값을 비교하자. 상하좌우 4개의 원소를 비교하므로 4번의 loop를 돌려야 한다. 비교 시 nx와 ny는 0보다 작거나 N보다 크면 안 된다. 존재하지 않는 값을 참조하는 것이기 때문이다.
상하좌우의 값들보다 현재 원소가 더 클 시 해당 원소는 봉우리가 될 수 있다.
이를 코드로 표현하면 아래와 같다.
for (let i=0; i<N; i++) {
for (let j=0; j<N; j++) {
let flag = true;
// 상하좌우 원소와 비교
for (let k=0; k<4; k++) {
// 비교할 원소의 x, y 좌표
const nx = i + dx[k];
const ny = j + dy[k];
// 봉우리 실패 요건
// 1. nx가 0보다 작거나 N보다 크다.
// 2. ny가 0보다 작거나 N보다 크다.
// 3. 현재 원소가 비교할 원소의 값(상하좌우 중 하나)보다 작다.
if(nx>=0 && nx<N && ny>=0 && ny<N && parsed[nx][ny]>=parsed[i][j]){
// 만약 위의 조건들을 모두 만족시키지 않으면 봉우리가 아니다.
flag = false;
break;
}
}
// 상하좌우 모든 조건을 충족시켰을 시 봉우리
if(flag) answer += 1;
}
}전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1).map(el => el.split(" "));
const N = Number(input.shift());
const parsed = input.map(arr => arr.map(target => Number(target)));
let answer = 0;
const dx=[-1, 0, 1, 0];
const dy=[0, 1, 0, -1];
for (let i=0; i<N; i++) {
for (let j=0; j<N; j++) {
let flag = true;
for (let k=0; k<4; k++) {
const nx = i + dx[k];
const ny = j + dy[k];
if(nx>=0 && nx<N && ny>=0 && ny<N && parsed[nx][ny]>=parsed[i][j]){
flag = false;
break;
}
}
if(flag) answer += 1;
}
}
console.log(answer);