[성실코딩 28일차] 백준 #16234 인구 이동

2018년 삼성전자 하반기 오전 시험 문제

쉬운데 어이없는 실수해서 틀렸었다

전역변수로 선언해서 사용하고 있는 배열 초기화할 때 크기 선언 잘해주기 ㅠㅠ

그냥 실수하지말기!!

#include < iostream >
#include < math.h >
#include < cstring >

using namespace std;

int map[51][51] = { 0, };
int N, L, R;
int cnt = 0; // answer

int mapGroup[51][51] = { 0, };
int group_idx = 0;
int mean[2500] = { 0, }; // 각 그룹의 인구 평균
int group_number = 0; // 그룹의 나라 수

// 동서남북
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};

void DFS(int _r, int _c, int _group_idx) {
	mapGroup[_r][_c] = _group_idx;
	mean[_group_idx] += map[_r][_c];
	group_number++;
	for (int k = 0; k < 4; k++) {
		int new_r = _r + dr[k];
		int new_c = _c + dc[k];
		// boundary check
		if ((new_r < 0 || new_r >= N) ||
			(new_c < 0 || new_c >= N)) {
			continue;
		}
		// 방문 경험 X
		if (mapGroup[new_r][new_c]==0) {
			// 차이 비교
			int diff = abs(map[_r][_c] - map[new_r][new_c]);
			if (L <= diff && diff <= R) {
				DFS(new_r,new_c,_group_idx);
			}
		}
	}
}

int main(void) {
	
	// 입력
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	// 연산
	while (1) {
		//1. map 확인하며 인구 이동 가능 표시 - 그룹화
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (mapGroup[r][c] == 0) // 아직 그룹화 되지 않음
				{
					for (int k = 0; k < 4; k++) { // 동서남북
						int new_r = r + dr[k];
						int new_c = c + dc[k];
						// boundary check
						if ((new_r < 0 || new_r >= N) ||
							(new_c < 0 || new_c >= N)) {
							continue;
						}
						// 차이 비교
						int diff = abs(map[r][c] - map[new_r][new_c]);

						if (L <= diff && diff <= R) {
							// 4방향 중 조건 만족할 때 최초의 한번만
							group_idx++;
							DFS(r, c, group_idx);
							// DFS에서 빠져나오면 평균구하기
							mean[group_idx] /= group_number; // ( groud_number =0 될 경우 X)
							// 초기화
							group_number = 0;
							// for문에서 빠져나가기
							break;
						}
					}
				}
			}
		}

		// 탈출조건 - map 모든 곳을 확인했는데 그룹이 없다면
		if (group_idx == 0) {
			break; // while문 빠져나옴
		}

		cnt++; // answer - 인구 이동 횟수

		// 2. 그룹화하여 평균 구한 인구로 map 설정
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (mapGroup[r][c] != 0) {
					map[r][c] = mean[mapGroup[r][c]];
				}
			}
		}

		// 초기화
		memset(mapGroup, 0, sizeof(int) * 51 * 51);
		memset(mean, 0, sizeof(int) * 2500);
		group_idx = 0;
	}
	
	cout << cnt << endl;
	return 0;
}