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

---

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

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

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

 

---

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

해답 코드 : 

 

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

typedef struct pos {

	int row;
	int col;

} pos;

typedef struct vir {

	int row;
	int col;
	int time;

} vir;

int N, K;

int map[50][50];
int backup[50][50];

// total viruses and number
pos virus[10];
int num_v; 
// active viruses
vector<pos> active;

int dR[4] = {-1, 1, 0, 0};
int dC[4] = {0, 0, -1, 1};

int ans;

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

// use this to restore map
void back_up(int dst[50][50], int src[50][50]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dst[i][j] = src[i][j];
		}
	}
}


// check viruses are spread all over the map
bool spread() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				return false;
			}
		}
	}

	return true;
}

// using bfs, paint map
void bfs() {

	back_up(backup, map);

	// queue for bfs
	deque<vir> myQ;
	vir t_pos;
	vir n_pos;
	int n_r, n_c;
	int max_sec = 10; // default value

	for (int i = 0; i < active.size(); i++) {
		t_pos = { active[i].row, active[i].col, 10};
		map[t_pos.row][t_pos.col] = -1;
		myQ.push_back(t_pos);
	}

	while (!myQ.empty()) {

		t_pos = myQ[0];

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

			n_r = t_pos.row + dR[dir];
			n_c = t_pos.col + dC[dir];

			if (isRange(n_r, n_c) && (map[n_r][n_c] == 0 || map[n_r][n_c] == 2)) {
				
				if (map[n_r][n_c] == 2 && spread()) {
					break;
				}
				
				map[n_r][n_c] = t_pos.time + 1;
				max_sec = max(map[n_r][n_c], max_sec);
				n_pos = {n_r, n_c, t_pos.time + 1 };
				myQ.push_back(n_pos);
			}


		}

		myQ.pop_front();
	}

	if (spread()) {
		
		if (ans == -1) {
			ans = (max_sec - 10);
		}
		else {
			ans = min(max_sec - 10, ans);
		}

	}

	back_up(map, backup);

}


// divide total viruses to pick "K" viruses
void divide(int cur) {

	// terminator
	if (active.size() == K) {
		bfs();
	}

	for (int i = cur; i < num_v; i++) {

		active.push_back(virus[i]);

		divide(i + 1);

		active.pop_back();

	}


}

int main() {

	cin >> N >> K;

	num_v = 0;
	pos t_v;
	ans = -1;

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

			cin >> map[i][j];
			if (map[i][j] == 2) {
				t_v = { i, j };
				virus[num_v] = t_v;
				num_v++;
			}

		}
	}

	// already spread
	divide(0);



	cout << ans << endl;

}

 

 

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

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

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