산봉우리
Coddy C 여정의 Fundamentals 섹션에 포함된 레슨 — 63개 중 62번째.
챌린지
지형도를 나타내는 정수 고도값의 2D 그리드가 주어집니다. 어떤 셀의 값이 인접한 모든 이웃(최대 8개: 북, 남, 동, 서 및 4개의 대각선)보다 엄격하게 클 경우, 그 셀을 봉우리(peak)라고 부릅니다.
규칙
- 8개의 이웃: 북, 남, 동, 서 및 4개의 대각선 방향을 모두 확인해야 합니다.
- 경계 셀: 셀이 가장자리나 모서리에 있는 경우 이웃이 8개보다 적습니다. 이 경우에도 존재하는 모든 이웃보다 엄격하게 크다면 봉우리입니다.
- 엄격하게 큼: 이웃의 고도가 현재 셀과 같다면, 현재 셀은 봉우리가 아닙니다.
입력
- 행과 열을 나타내는 두 정수
N과M. - 정수로 이루어진
N*M그리드
출력
- 봉우리의 총 개수를 나타내는 정수.
- 각 봉우리의 좌표(행과 열, 0부터 시작), 행을 기준으로 먼저 정렬하고 그 다음 열을 기준으로 정렬합니다.
예를 들어 다음과 같은 입력의 경우:
5 5
1 2 1 3 4
5 1 1 1 1
1 1 9 1 1
2 1 1 1 2
1 3 1 4 1출력은 다음과 같습니다:
5
0 4
1 0
2 2
4 1
4 3설명 봉우리는 다음 위치에서 발생합니다:
- 고도가 4인 (0,4): 이웃(3, 1, 1)보다 큽니다.
- 고도가 5인 (1,0): 이웃(1, 2, 1, 1, 1)보다 큽니다.
- 고도가 9인 (2,2): 주변의 모든 8개 1보다 큽니다.
- 고도가 3인 (4,1): 이웃(2, 1, 1, 1, 1)보다 큽니다.
- 고도가 4인 (4,3): 이웃(1, 1, 1, 2, 1)보다 큽니다.
직접 해보기
#include <stdio.h>
#define MAXN 100
#define MAXM 100
int N, M;
int grid[MAXN][MAXM];
/**
* (r, c) 위치의 셀이 산봉우리이면 1을, 그렇지 않으면 0을 반환합니다.
* 산봉우리는 존재하는 모든 이웃보다 엄격하게 더 커야 합니다.
*/
int is_peak(int r, int c) {
// TODO: 8개 이웃의 상대적 위치를 정의하세요
// (북, 남, 동, 서 및 4개의 대각선).
// TODO: 각 이웃을 루프로 확인하세요.
// 중요 힌트: grid[nr][nc]를 확인하기 전에, 반드시
// nr과 nc가 범위 내에 있는지(0 ~ N-1 및 0 ~ M-1) 확인해야 합니다.
return 1; // 임시 반환값
}
int main() {
// 차원 읽기
if (scanf("%d %d", &N, &M) != 2) {
return 1;
}
// TODO: 중첩 루프를 사용하여 표준 입력(stdin)으로부터 그리드 값을 읽으세요.
// TODO: 그리드의 모든 셀 (i, j)을 반복하세요.
// 만약 is_peak(i, j)가 참이면, 해당 좌표를 저장하세요.
// 출력하기 전에 결과를 저장하기 위해 peak_r[MAXN*MAXM]와 peak_c[MAXN*MAXM]
// 같은 두 개의 배열을 사용할 수 있습니다.
// TODO: 산봉우리의 총 개수를 출력하세요.
// TODO: 저장된 각 (행, 열) 쌍을 출력하세요.
// 행 다음에 열 순서로 반복하므로, 이미 정렬되어 있을 것입니다!
return 0;
}