✏️ 문제
설명
지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다.
각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.
격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.
입력
첫 줄에 자연수 N이 주어진다.(2<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.
출력
봉우리의 개수를 출력하세요.
예제입력
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
예제출력
10
✏️ 코드
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int [][] arr = new int[N][N];
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
arr[i][j] = sc.nextInt();
}
}
System.out.print(solution(N, arr));
}
public static int solution(int N, int[][] arr) {
int[] dx = {-1,0,1,0};
int[] dy = {0,1,0,-1};
int answer = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
boolean flag = true;
for (int k=0; k<4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx>=0 && nx<N && ny>=0 && ny<N && arr[nx][ny] >= arr[i][j]) {
flag = false;
break;
}
} // end for3
if (flag) {
answer++;
}
} // end for2
} // end for1
return answer;
}
}
int[] dx ={-1,0,1,0} 와 int[] dy = {0,1,0,-1} 을 사용해서 arr[i][j]의 상하좌우에 있는 숫자를 구할 것이다.
행을 i, 열을 j라고 한다면 1행 1열에는 7이 있을 것이다. ex)arr[1][1], i=1, j=1이다.
이제 순서대로 상하좌우에 있는 숫자의 위치는
arr[0][1], arr[2][1], arr[1][0], arr[1][2] 이다.
이를 보면 일종의 규칙이 있다.
i+dx[k] 과 j+dy[k] (k=0~4) 를 돌면
순서대로 i와 j이가 1일때
(0,1), (1,2), (2,1), (1,0) 이 나온다.
위에서 상하좌우에 있는 숫자의 좌표이다.
nx=i+dx[k], ny=j+dx[k] 로 선언한다면(nx는 행 좌표 번호, ny는 열 좌표 번호)
해당 코드에서 해당 좌표에 있는 숫자의 인덱스는 arr[nx][ny]라고 할 수 있다.
arr[i][j] 에 위치한 숫자가 상하좌우보다 큰 경우 개수를 늘려주면 된다.
반대로 하나라도 arr[i][j] 보다 크다면 개수를 늘릴 필요가 없기때문에 for문에서 탈출하면 된다.
해당 좌표가 봉우리인지 확인하기 위해서 flag변수를 통해서 flag가 true일 경우에만 더해주면 된다.
여기서 주의할 점은 격자판의 가장자리에 있는 숫자들은 상하좌우 중 한 곳에서 비교할 대상이 없어지기 때문에 에러가 발생한다.
그래서 if조건에 조건을 추가해주어야한다.
가장자리는 0으로 초기화한다고 가정하기 때문에 x와 y좌표에 해당하는 nx 그리고 ny는 0보다 크거나 같아야한다.
nx >= 0 && ny >= 0
또한 x좌표와 y좌표는 배열의 크기보다 클 수가 없다.
nx < N && ny < N
조건을 추가하면 된다.
위의 두 조건을 arr[i][j] <= arr[nx][ny]
보다 앞에 쓰는 경우는 애초에 배열의 범위를 넘어가거나 배열의 범위를 넘는 좌표이면 봉우리일수가 없기 때문이다.
정리
격자판에서 상하좌우 구하려면
dx[] = {-1,0,1,0}
dy[] = {0,1,0,-1}
좌표는
nx = i + dx[k]
ny = j + dy[k]
