삼성 SW 역량테스트 기출문제인 백준 사이트의 17142번 문제 연구소 3을 풀이해보겠습니다. 연구소 3 문제는 조합과 BFS를 사용하여 문제 풀이를 할 수 있습니다. 요즘 기출에는 단일 알고리즘보다는 이 문제처럼 복합 문제 출제가 많습니다.
2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 14502번] 연구소 (조합, BFS)
2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 17142번] 연구소 3 (조합, BFS)
안녕하세요. 지칸입니다.
오늘 풀어볼 기출문제는 17142번 연구소 3입니다. 기존 14502번 연구소 문제와 흡사한 문제로 보입니다. 천천히 문제를 풀어보겠습니다.
1) 문제 이해
2) 구조 잡기
3) 주의 사항
저의 결론) BFS + 조합의 문제입니다. 기존 기출과 유사문제이고 표현만 다르지 이런 복합 문제는 자주 나옵니다.
1) 문제 이해
문제 출처 : www.acmicpc.net/problem/17142
문제)
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1 ×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
-> 문제 해석
- 2차원 NxN MAP 배열 사용
- 사방으로 확산된다? BFS 문제
- 정점 간 연결을 좌표상 4방향이고 벽이 있으면 못 감
- 총 바이러스 중 M개만 활성화? 조합 문제
- 각 최초 원점 M개가 별도로 BFS를 돌려야 함
- 사방으로 확산되니까 BFS 큐에 최대 4개 정점을 추가하고 이들은 전부 같은 초를 가짐
- 1초간 동작에 같은 초로 들어간 정점은 다 빼야 함-> 같은 초 정점들이 다시 이웃들 전부 큐에 등록하고 1초 증가
- 완료 시간 6에서 *를 보면 4초에서 5초로 증가 없이 끝남 -> 큐에서 빼기 전에 이미 완료됐는지 체크(비활성화 포함)
| 주어진 맵 | 완료 시간 6 | 완료 시간 4 |
| 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2 |
* 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 * |
0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 * - 3 2 3 4 * |
입력)
첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.
둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.
-> 입력 해석
- 최대 맵의 크기는 50x50
- 초기 활성화 바이러스 수는 M개 (BFS 병렬로 돌려야 하는데 최대 10개를 돌릴 수 있음) -> BFS 큐 배열 사용(10 사이즈)
- 0,1,2의 의미 확인, define으로 사용하는 게 의미가 확실함
출력)
연구소의 모든 빈칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.
-> 출력 해석
- 모든 조합을 살펴볼 때 min값을 계속 체크, 모든 조합 끝났는데 완료된 적 없으면 -1
2) 구조 잡기
맨 처음 진행할 것은 입력 구조를 잡아주는 것입니다. 아래 포스팅에서 이미 설명을 한 적이 있습니다.
2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비
2-1) 초기 세팅
백준의 구조는 테스트 케이스가 없기 때문에 그 부분은 생략하시면 되고 기본적인 맵 상태를 만들어 봅니다.
#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 50
#define MAX_M 10
#define VIRUS 2
#define WALL 1
#define EMPTY 0
#define MAX_C 123456789
struct coor
{
int y;
int x;
};
int N;
int M;
int originalmap[MAX_N][MAX_N]={0,};
vector<coor> virusarr; //초기 총 바이러스의 위치
int sol = MAX_C; // 최소시간를 저장할 변수
int main(){
cin >> N >> M;
int temp;
coor tempVirus;
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
cin>>temp;
originalmap[y][x] = temp;
// 바이러스 위치 저장
if (temp == VIRUS) {
tempVirus.x = x;
tempVirus.y = y;
virusarr.push_back(tempVirus);
}
}
}
/*
풀이 동작
function()
*/
if (sol == MAX_C)
cout << "-1"; //풀이 동작이 끝났는데 여전히 초기값이면 -1
else
cout << sol;
return 0;
}입력으로부터 define을 정의하고 NxN 2차원 배열 map을 만들어 줍니다. 그리고 벡터를 사용하여 바이러스의 위치를 전부 저장해 줍니다. 우리는 coor 구조체를 사용하여 정점의 위치 좌표를 들고 다닐 겁니다. 이렇게 하지 않고 각 정점 인덱스를 표기하여 인덱스만 들고 다녀도 됩니다.
이중 for문으로 입력을 전부 받고, 그 와중에 바이러스 위치를 따로 저장합니다. 그리고 어떤 풀이과정을 거치고 최소 시간인 sol 변수의 초기값 여부를 체크하여 -1 사항을 반영할 수 있습니다.
2-2) 조합 구현하기
풀이 동작에 맨 처음은 조합을 구현하는 겁니다. 총 비활성화 바이러스 중 M개를 선택하고 각 경우의 수마다 완료 시간을 확인하는 과정이 필요합니다. 우리는 M개 선택을 조합으로 풀이하고 각 경우의 수마다 완료시간 확인하는 과정은 BFS를 사용할 예정입니다.
//... 기존 코드 생략...
vector<int> flagComb; //조합 구현시 내가 선택한 인덱스 체크용 변수
vector<coor> virusselectarr; //virusarr 배열 중 M개 선택한 바이러스 좌표 저장용 변수
void operation() { //M개를 선택완료시 호출되는 함수
// 조합 잘 나왔는 지 테스트
for (int i = 0; i < virusselectarr.size(); i++) { // 사이즈가 항상 M 임
cout << virusselectarr[i].y << ", " << virusselectarr[i].x << endl;
}
cout << endl;
// BFS 시작
}
void comb(int n, int r) {
if (n == r) {
for (int i = 0; i < n; i++) {
flagComb[i] = 1;
}
for (int i = 0; i < virusarr.size(); i++) {
if (flagComb[i] == 1) virusselectarr.push_back(virusarr[i]);
}
operation();
virusselectarr.clear();
for (int i = 0; i < n; i++) {
flagComb[i] = 0;
}
return;
}
if (r == 1) {
for (int i = 0; i < n; i++) {
flagComb[i] = 1;
for (int j = 0; j < virusarr.size(); j++) {
if (flagComb[j] == 1) virusselectarr.push_back(virusarr[j]);
}
operation();
virusselectarr.clear();
flagComb[i] = 0;
}
return;
}
flagComb[n - 1] = 1;
comb(n - 1, r - 1);
flagComb[n - 1] = 0;
comb(n - 1, r);
}
int main(){
//... 기존 코드 생략...
for (int i = 0; i < virusarr.size(); i++) {
flagComb.push_back(0);
}
//조합으로 총 바이러스 중 M개 뽑기
comb(virusarr.size(), M);
if (sol == MAX_C)
cout << "-1"; //풀이 동작이 끝났는데 여전히 초기값이면 -1
else
cout << sol;
return 0;
}코드가 설명할수록 계속 길어지기 때문에 기존 작성된 코드는 생략하도록 하겠습니다.. 조합 알고리즘은 이전 포스팅에 설명했습니다. 이 기본 틀은 숙달되어야 하고 여기서는 조합 코드의 설명은 생략하겠습니다.
2021.04.01 - [알고리즘/SW역량테스트] - (4장-2) 조합(Combination) 알고리즘이란?
조합 알고리즘 포스팅에서 나온 예제를 완전 그대로 사용했습니다. M개를 찾았을 때 어떤 동작을 할지를 operation 함수로 표현해봤습니다. 여기까지 잘 동작하는지 확인을 위해 프린트 동작을 넣어봤습니다. 여기서 M개의 바이러스 위치가 잘 출력되는지 체크해봅니다.
2-3) BFS 구현하기
operation 함수에서 이제 BFS를 시작하면 됩니다. 입력에서 분석한 것처럼 1초 동안 복수의 초기 활성 바이러스에서 동시에 확산되어야 합니다. 우리는 큐 배열을 만들어서 BFS 동작을 해야 합니다. 이것은 이전 포스팅한 내용에서 응용을 해야 합니다.
2021.03.16 - [알고리즘/SW역량테스트] - (3장-2) BFS(너비우선탐색) 알고리즘이란?
매 조합마다 MAP을 건드려야 하니 원본은 그대로 두고 CopyMap을 사용합시다. M개를 찾았으면 그때마다 원본 Map으로부터 CopyMap으로 복사하는 초기화 동작을 구현해줍니다.
#define VIRUSc -2
#define WALLc -1
#define EMPTYc -3
int countEmpty;
int copymap[MAX_N][MAX_N] = { 0 , };
void copy() {
countEmpty = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (originalmap[i][j] == WALL) copymap[i][j] = WALLc;
else if (originalmap[i][j] == VIRUS) {
copymap[i][j] = VIRUSc;
}
else {
copymap[i][j] = EMPTYc;
countEmpty++;
}
}
}
}
void operation() {
copy(); // copymap 초기화
//BFS의 스타트
}
CopyMap에서는 0,1,2,3 쭉 좌표마다 초를 입력해야 하기 때문에 벽, 바이러스, 빈 공간에 대항 define를 다시 정의해 줍니다. (이 부분에 대해선 다양한 접근방법이 있을 것 같습니다.) countEmpty는 추후 큐에서 뺄 때마다 더 이상 빈칸이 없는지 체크하기 위한 용도로 사용됩니다. 이 변수 없이 그때그때 2차원 배열 전부 빈칸 여부를 체크하면 폭발적인 계산량 증가가 존재하기 때문에 저는 이런 변수를 사용합니다.
이제 BFS 내부를 살펴봅시다. 이 문제의 핵심은 BFS입니다. 코드에 열심히 주석을 만들어 봤습니다.
#include <queue>
#define MAX_Dir 4
bool checkmaprange(coor yx) {
if ((0 <= yx.y && yx.y < N) && (0 <= yx.x && yx.x < N))
return true;
return false; //범위를 벗어나면 false
}
bool checkfirstvisit(coor yx) {
if (copymap[yx.y][yx.x] == EMPTYc || copymap[yx.y][yx.x] == VIRUSc) {
return true; //빈칸이거나 비활성화 바이러스가 있으면 true
}
return false;
}
void BFS() {
int count = 0;
int qtotalsize = 0;
queue<coor> q[MAX_M];
for (int i = 0; i < M; i++) { // M개의 바이러스 스타트니까 M개 배열로 병렬 동작처럼 구현
q[i].push(virusselectarr[i]); //첫 바이러스를 각 큐에 시작점으로 넣기
copymap[virusselectarr[i].y][virusselectarr[i].x] = count; //첫 바이러스 스타트 0, copymap에 값을 입력하여 이미 방문했는지 체크하는 용도로도 쓰임
qtotalsize += q[i].size(); //전체 큐 사이즈가 0이면 while를 종료할 것임
}
coor current;
coor candidate;
int dy[4] = { 0,-1,0,1 }; //이런 좌표문제에서 많이 쓰임, 순서는 왼,위,오,아
int dx[4] = { -1,0,1,0 };
bool Isexceed = false; // 이전 조합의 완료시간을 넘을 경우 더 진행할 필요가 없음
while ((qtotalsize != 0) && (countEmpty > 0) && !Isexceed) { //모든 큐가 0이면 종료, 더이상 빈칸 없으면 종료
qtotalsize = 0;
count++;
for (int i = 0; i < M && !Isexceed; i++) { // 병렬로 동시에 진행할 큐 각자 for문
int qsize = q[i].size();
for (int k = 0; k < qsize && !Isexceed; k++) {// 같은 초인 정점들은 전부 pop해야함
current = q[i].front();
for (int j = 0; j < MAX_Dir && !Isexceed; j++) { //4가지 방향의 정점 체크
candidate.y = current.y + dy[j];
candidate.x = current.x + dx[j];
if (checkmaprange(candidate) && checkfirstvisit(candidate)) {//맵 범위안쪽이여야 하고 처음 방문하는 정점이어야 함
q[i].push(candidate); //새로운 정점 큐에 추가
if (copymap[candidate.y][candidate.x] == EMPTYc) {
countEmpty--; //빈칸 방문시 감소
}
copymap[candidate.y][candidate.x] = count; //지금 정점들의 시간 업데이트, 방문표시이기도 함
if (sol <= count)
Isexceed = true; // 이미 이전 조합의 시간보다 초과되면 더 할 필요 없음
}
}
q[i].pop();
}
qtotalsize += q[i].size(); //큐 사이즈 다시 체크
}
}
if ((countEmpty == 0) && !Isexceed) { //전 칸 확산됐을 때 이전보다 최소값인지 확인
if (sol > count)
sol = count;
}
}티스토리 코드 블록 기능을 처음 써보는데 들여 쓰기가 이상하네요;; 이건 차차 배우면서 고쳐보겠습니다. checkmaprange, checkfirstvisit 함수는 별도로 만들었습니다. BFS안에 있어도 상관은 없습니다.
기존 BFS 알고리즘과 다른 부분이 큐를 배열로 정의하는 부분입니다. M개만큼 동시에 확산되기 때문입니다. 초기 스타트 정점을 넣어주고 visit 배열은 따로 없습니다. copymap에 count를 입력하는 것이 방문 여부 확인용에 쓰입니다. 이렇게 초기 동작을 넣어주고 while이 시작됩니다.
기존에는 큐가 비었는가만 체크했다면 이번에는 3가지 조건이 있습니다.
- 큐가 비었는가 -> 기본 BFS의 조건
- 빈칸이 없는가 -> 비활성화 바이러스도 체크 요소이기 때문에 매 확산 시 체크, 이게 없다면 비활성화만 큐에 남아있을 때 또 1초가 지나버림, 그럴 필요가 없음
- 이미 시간이 초과했는가 -> 불필요한 이후 동작을 생략하기 위해 사용됨, 없어도 동작엔 상관없음
같은 시간에 들어온 정점들은 전부 pop 해야 하기 때문에 for문이 한 개 더 들어갔습니다. 기존 BFS보다 for문이 많아졌네요..;; 10x4x4가 최대 for문 수이기 때문에 무리 갈 정도는 아닙니다.
3) 주의사항
백준 문제는 테스트 케이스가 아닌 단일 입력에 대한 문제이기 때문에 초기화에 신경을 덜 써도 됩니다. 하지만 삼성 시험에서는 TC 수만큼 반복을 하기 때문에 반복할 때 기존에 사용된 값들이 다음 문제에서 영향이 없는지 꼭 체크해야 합니다.
나머지는 코드에 주석으로 설명하고 있습니다. 혹시 이해 안 되는 부분이 있다면 댓글 주세요.
'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글
| [백준 14888번] 연산자 끼워넣기 (순열) (0) | 2021.04.16 |
|---|---|
| [백준 14503번] 로봇 청소기 (시뮬레이션) (0) | 2021.04.16 |
| [백준 14889번] 스타트와 링크 (조합) (0) | 2021.04.14 |
| [백준 15686번] 치킨배달 (조합) (0) | 2021.04.08 |
| [백준 14502번] 연구소 (조합, BFS) (0) | 2021.04.08 |
댓글