SW 역량테스트 - [백준] 인구 이동 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/16234

해답 코드 : 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

typedef struct pos {
	int row;
	int col;
}pos;


typedef struct cell {
	int row;
	int col;
	int val;
}cell;


int map[50][50];
bool bar[50][50][4];
bool merged[50][50];

// check whether people moved or not
bool move_flag;

// how many times people moved
int ans;

vector<pos> my_union;
vector<cell> update_cell;

// right, down, left, up
int dR[4] = {0, 1, 0, -1};
int dC[4] = {1, 0, -1, 0};

int N, L, R;

bool isRange(int r, int c) {

	if (r < 0 || r >= N || c < 0 || c >= N) {
		return false;
	}
	else return true;
}

bool lr(int x, int y) {
	if ( (abs(x - y) >= L) && (abs(x - y) ) <= R) {
		return true;
	} else return false;
}

// using vector my_union, update population
// update ans += 1
// if vector is not empty, move_flag -> true
void merge() {
	
	int newVal = 0;
	int sum = 0;
	cell temp;

	if (my_union.size() <= 1) {
		return;
	}
	else {
		//ans++;

		for (int i = 0; i < my_union.size(); i++) {
			sum += map[my_union[i].row][my_union[i].col];
		}
		
		newVal = sum / my_union.size();

		/*
		for (int i = 0; i < my_union.size(); i++) {
			map[my_union[i].row][my_union[i].col] = newVal;
		}
		*/

		for (int i = 0; i < my_union.size(); i++) {
			temp = { my_union[i].row , my_union[i].col, newVal};
			update_cell.push_back(temp);
		}


	}

}

// make bar[50][50][4] array 
// if there is no open bar, return -1
int make_bar() {

	int flag = -1;
	int n_r, n_c;

	// check 4 end point

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			for (int dir = 0; dir < 4; dir++) {
				n_r = i + dR[dir];
				n_c = j + dC[dir];

				if (isRange(n_r, n_c) && lr(map[i][j], map[n_r][n_c])) {

					bar[i][j][dir] = true;
					flag = 0;
				} 
				else {
					bar[i][j][dir] = false;
				}

			}

		}
	}


	return flag;
}

void dfs(int c_r, int c_c) {
	
	int n_r, n_c;
	pos t_pos;

	if (merged[c_r][c_c]) {
		return;
	} 
	else {

		merged[c_r][c_c] = true;
		t_pos = {c_r, c_c};
		my_union.push_back(t_pos);

		for (int dir = 0; dir < 4; dir++) {

			n_r = c_r + dR[dir];
			n_c = c_c + dC[dir];

			if (isRange(n_r, n_c) && bar[c_r][c_c][dir]) {
				dfs(n_r, n_c);
			}


		}
	}

}


// search through map using bar
// merge "union", up the 'merged' flag for each area
// if there is no open bar, return -1
int dfs_map() {

	int flag = -1;

	int n_r, n_c;

	// If no union is made, return -1
	if (make_bar() == -1) {
		return -1;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			dfs(i, j);

			merge();

			my_union.clear();
		}
	}

	// restore merged
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			merged[i][j] = false;
		}
	}

	// update cells
	for (int i = 0; i < update_cell.size(); i++) {
		map[update_cell[i].row][update_cell[i].col] = update_cell[i].val;
	}

	update_cell.clear();

	return 0;
}




int main() {

	cin >> N >> L >> R;

	// N is 1
	if (N == 1) {
		cout << 0 << endl;
		return 0;
	}

	move_flag = false;
	int temp_ans = 0;
	ans = 0;
	

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	while (dfs_map() != -1) {
		ans++;
	}

	cout << ans << endl;

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제