문제

안녕하세요.
백준에서 삼성 SW 역량 테스트 기출 문제집에 게시된 16234번 톱니바퀴 문제 풀이를 소개하겠습니다.

이번 문제는 2차원 배열 내에서 변화가 몇 번 만큼이나 발생하는지 확인하는 문제 입니다.
세부적으로는 배열에서 특정 구역 내에 있는 숫자들의 평균을 구해야 합니다.
문제에서 주어진 조건에 맞추어 BFS(넓이 우선 탐색)를 진행하여 구역을 탐색하면 되겠습니다.

풀이 코드는 사람이 쉽게 이해 할 수 있는 코드를 지향하여 작성하였습니다. 따라서 최적의 성능을 가지는 코드가 아닐 수 있습니다.

주어진 정보

  • N : 2차원 배열의 가로, 세로 길이
  • L : 연합이 가능한 조건 중 최소 차이
  • R : 연합이 가능한 조건 중 최대 차이
  • 배열의 요소 : 해당 칸(나라)의 인구

해결 방향

먼저 2차원 배열의 모든 요소를 순회 하되, 바로 인접한 나라들의 값을 변경하려고 하면 해결할 수가 없습니다.
문제 조건에 맞는 연합 리스트를 만들고 하나의 연합의 총 인구를 계산후 배열의 값을 갱신하여 해결할 수 있습니다.

풀이

풀이 코드

#include <iostream>
#include <vector>

using namespace std;

int dd[][4] = { {-1,0,1,0},{0,1,0,-1} };	// 확인 방향에 따른 인덱스 변화 값

vector < vector <int> > arr;	// 땅 배열
int N,L,R; // N : 땅 크기, L : 인구 차이 최저 기준, R : 인구 차이 최대 기준


bool check_boundary(int c, int r) {
	if (c < 0 || c >= N) return false;
	if (r < 0 || r >= N) return false;
	return true;
}

vector<vector<pair<int, int>>> get_unions() {
	vector < vector <bool> > arr_visited = vector< vector <bool> >(N, vector <bool>(N, 0));	// 국가 방문 기록 배열
	vector<vector<pair<int, int>>> unions = vector<vector<pair<int, int>>>();				// 연합으로 구성된 국가들 리스트
		
	vector<pair<int, int>> union_ = vector<pair<int, int>>();	// 연합 임시 저장용
	vector<pair<int, int>> queue = vector<pair<int, int>>();	// 탐색 임시 저장용

	// 모든 땅에 대해 연합 국가들을 탐색
	for (int c = 0; c < N; c++) {
		for (int r = 0; r < N; r++) {
			queue.clear();
			union_.clear();

			// 탐색 시작할 위치에 이미 방문한 기록이 있으면 패스
			if(arr_visited[c][r] == 1) 
				continue;

			// 탐색 큐에 추가
			queue.push_back(pair<int, int>(c, r));
			arr_visited[c][r] = 1;

			// BFS
			while (true) {
				if (queue.size() == 0) break;	// 탐색 하고자 하는 큐가 비어있다면 종료

				pair<int, int> pos = queue.front();	// 탐색된 현재 위치
				queue.erase(queue.begin());			// 맨 앞의 요소 제거
				union_.push_back(pos);				// 조건에 만족하는 국가 추가

				// 현재 위치 기준으로 네 방향 탐색.
				for (int way = 0; way < 4; way++) {
					int c_ = pos.first + dd[0][way];
					int r_ = pos.second + dd[1][way];

					// 배열 밖을 벗어나는 경우, 이미 방문한 경우, 인구 차이 조건 맞지 않은 경우 패스
					if (check_boundary(c_, r_) == false) continue;
					if (arr_visited[c_][r_] == 1) continue;

					int diff_pop = abs(arr[pos.first][pos.second] - arr[c_][r_]); // 인구 차이 계산
					if (diff_pop < L || diff_pop > R) continue;

					// 모든 조건에 만족하는 경우 해당 국가에 방문
					queue.push_back(pair<int, int>(c_, r_));
					arr_visited[c_][r_] = 1;
				}
			}

			// 국경개방 국가가 두 군데 이상이라면, 연합 리스트에 추가
			if (union_.size() > 1) unions.push_back(union_);
		}
	}

	return unions;
}


void move_population(vector<vector<pair<int, int>>> unions) {

	// 개방된 연합들에 대해 반복
	for (auto union_ : unions) {
		int sum = 0;
		int total = union_.size();

		// 연합들의 총 인구수 계산
		for (auto pos : union_) {
			sum += arr[pos.first][pos.second];
		}

		// 이동된 인구 계산
		int pop = int(sum / total);

		// 연합들의 인구수 갱신
		for (auto pos : union_) {
			arr[pos.first][pos.second] = pop;
		}
	}
}

int solution() {
	int day = 0;

	while (true) {
		vector<vector<pair<int, int>>> unions = get_unions();

		if (unions.size() > 0) {
			day++;
			move_population(unions);
		}
		else {
			break;
		}
	}

	return day;
}

int main() {
	cin >> N >> L >> R;

	arr = vector< vector <int> >(N, vector <int>(N, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}
	// 초기화 끝


	cout << solution() << endl;

	return 0;
}

해설

  • solution() : 연합이 반복적으로 구성될 때, day를 증가 시키며 인구 이동
  • get_unions() : 조건에 해당하는 연합들의 리스트를 반환
    • vector < vector > arr_visited : 중복 탐색 방지를 위한 방문 맵
    • vector<vector<pair<int, int»> unions : 같은 연합에 포함되는 나라들의 인덱스 정보를 저장
    • BFS : 배열의 모든 인덱스를 시작 위치로 하여 인구 차이가 조건에 맞으면 큐에 추가하면서 탐색을 진행. 더 이상 방문할 나라가 없다면 방문했던 나라들을 연합으로 묶어 저장.
  • move_population() : 저장된 각 연합들 내에서 인구 이동을 시킴

앗 이걸 생각 못했네?

  • BFS 코드 작성을 많이 해본 분들에게는 당연한 이야기 일수도 있지만…
    • BFS 진행 중에 발생하는 대부분의 에러는 배열의 인덱스 초과 였던 것 같다.
    • 인덱스 체크

      , 중복 방문, 탐색 중단 조건. 이 세가지만 주의 하면 사소한 실수는 줄일 수 있다.

  • ‘이상’, ‘이하’라는 조건에 맞게 ‘<=’, ‘>=’ 비교연산자 실수에 조심해야 한다.

다른 풀이

16234번 인구이동 1차 풀이

기타 다른 문제 풀이 코드 (github)