[여섯번째 문제] 백준 / 1245 : 농장관리

이 문제도 참 많이도 틀렸다.
하지만 좌절하지 말자 , 인생은 기니까.
( 코딩할 수 있는 시간은 짧지만 논외로 치자)

// N X M 농장 -> 2차원배열
// 산봉우리는 몇개가있는가?
~~텍스트~~

// 산봉우리의 정의 - 같은높이를 가지는 (최대높이점 구하는게 아님)
/*8 7
9 3 2 2 1 0 9
3 3 3 2 1 0 9
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 9 9 1 1 0
0 1 1 1 9 1 0*/

/*8 7
4 1 2 2 1 0 1
1 1 1 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0*/

//3개
// 재귀적으로 해결 
// 최대 100 * 70

#include <iostream>

// 0 9
// 9 10
// 10 10
// 2 54
// 3?

using namespace std;

int numMountain = 0;
int gameBoard[101][71];
int check[101][71];
int N, M;
int add = 0;
int dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };

void changeBoard(int gameBoard[101][71], int check[101][71], int i, int j) {
	check[i][j] = 1;
	for (int z = 0; z < 8; z++) {
		if (check[i + dir[z][0]][j + dir[z][1]] != 1 && i + dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1) {
			if (gameBoard[i + dir[z][0]][j + dir[z][1]] == gameBoard[i][j]) {
				check[i + dir[z][0]][j + dir[z][1]] = 1;
				changeBoard(gameBoard, check, i + dir[z][0], j + dir[z][1]);
			}
		}
		if (i+dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1 && gameBoard[i + dir[z][0]][j + dir[z][1]] > gameBoard[i][j]) {
			add = 1;
		}
	}
}

void checkBoard(int gameBoard[100][71], int check[100][71], int i, int j) {
	int temp = gameBoard[i][j];
	add = 0;
	// gameBoard[i][j] = 현재값
	for (int q = 0; q < 8; q++) {
		if (i + dir[q][0] >= 0 && i + dir[q][0] <= N - 1 && j + dir[q][1] >= 0 && j + dir[q][1] <= M - 1) {
			if (gameBoard[i + dir[q][0]][j + dir[q][1]] > gameBoard[i][j]) {
				changeBoard(gameBoard,check,i,j);
				return; // 인접격자가 본인보다 크다면 , 봉우리일수가 없으므로 인접한 모든 격자를 change
			}
			// return이 안되었다면, 본인이 가장 같거나 크다는 뜻
		}
	}
	changeBoard(gameBoard, check, i, j);
	
	if (temp != 0 && add == 0) {
		numMountain += 1;
	}
	
}

int main() {

	numMountain = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> gameBoard[i][j];
			check[i][j] = 0;
		}
	}


	// 모든 배열에 대해 함수를 시도
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (check[i][j] != 1) { // 봉우리체크가 끝나지 않는 지역의 경우
				checkBoard(gameBoard, check, i, j);
			}
		}
	}
	cout << numMountain;
	return 0;
}

우선 한가지 습관을 들이기로 했다.

무작정 시작하기 전에, 주석으로 내가 이해한 바를 최대한 써보는 것

이 문제는 반례를 확인하는것이 너무 어려웠는데 알고리즘의 논리를 잘못 구현했기 때문이다.

3 3
1 0 1
1 1 6
2 2 2

이 case를 봉우리가 2개라고 판단했는데 , 상단의 checkBoard함수에서

if (i+dir[z][0] >= 0 && i + dir[z][0] <= N - 1 && j + dir[z][1] >= 0 && j + dir[z][1] <= M - 1 && gameBoard[i + dir[z][0]][j + dir[z][1]] > gameBoard[i][j])

6과 붙어있는 2는 봉우리가 아니라고 판단해야 하는 위의 조건문이 처음에는 check(방문)을 했는지도 확인하고 있었다.
이건 말이 안된다.
방문은 같은 숫자들이 연속으로 있을때 하나의 봉우리로 인식하고 중복으로 방문하지 않기 위해 존재한다.

주변에 더 큰 봉우리가 있는지 판단 할때는 그 봉우리를 방문 했는지 안했는지를 판단할 필요가 없는 것이다.

개인적으로는 찾기도 힘든 논리 오류 였지만, 그래도 아예 의미가 없는건 아니었다.

test case를 임의로 작성하는 능력을 조금 기르게 되었다.

이것은 비단 알고리즘 문제풀이를 진행할 때만이 아니라, 현재 개인적으로 하고 있는 임베디드 코딩 드론 프로젝트에서 코딩을 할때도 유의미하게 사용할 수 있는 능력이라고 본다.

사실 코딩테스트나 아니면 웹페이지 / 임베디드 코딩이라도 돌려보고 오류를 찾는건 제정신이 아니다. 돌리기 전에 오류를 찾는게 가장 중요하다.