[백준 14502번] 연구소 (조합, BFS)

삼성 SW 역량테스트 기출문제인 백준 사이트의 14502번 문제 연구소를 풀이해보겠습니다. 연구소 문제는 조합과 BFS를 사용하여 문제 풀이를 할 수 있습니다. 기존 17142번 연구소 3 문제와 유사한 것을 볼 수 있습니다. 본 포스팅이 난이도는 더 쉽습니다.

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 14502번] 연구소 (조합, BFS)

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 17142번] 연구소 3 (조합, BFS)

안녕하세요. 지칸입니다.

오늘 풀어볼 기출문제는 14502번 연구소입니다. 기존 17142번 연구소 3 문제와 흡사한 문제이며 난이도는 본 포스팅 문제가 더 쉽습니다. 기출 연도도 꽤 지난 문제입니다. 천천히 문제를 풀어보겠습니다.

1) 문제 이해

2) 구조 잡기

3) 주의 사항

저의 결론) 조합 + BFS 문제입니다. 연구소, 연구소 3은 문제가 매우 비슷합니다.

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/14502

문제)

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1 ×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

0은 빈칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈칸으로 퍼져나갈 수 있다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

주어진 맵	2행 1열, 1행 2열, 4행 6열에 벽 추가	최종 결과
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 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0	2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0	2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

-> 문제 해석

2차원 배열 NxM 맵 생성
빈 칸 중 3개를 선택해서 벽을 생성 -> 조합 문제
바이러스는 사방으로 확산 -> BFS문제
최소 맵에서 빈칸 3개를 선택하는 방법, 경우의 수마다 맵이 필요 -> copy MAP 생성
빈칸 수 카운팅, BFS 끝났을 때 빈칸수가 최대가 되는 경우 찾기 -> 이전까지 정답과 이번 정답과의 크기 비교

입력)

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈칸의 개수는 3개 이상이다.

-> 입력 해석

맵의 크기, 직사각형 구조, y축, x축 혼동하면 안 됨

출력)

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

-> 출력 해석

빈칸 중 3개 선택하는 모든 경우의 수를 진행하면서 max값 1개만 비교하며 계속 들고 가기

2) 구조 잡기

맨 처음 진행할 것은 입력 구조를 잡아주는 것입니다. 아래 포스팅에서 이미 설명을 한 적이 있습니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

2-1) 초기 세팅

이런 2차원 맵 문제는 거의 동일합니다. cin으로 input.txt를 받아와서 맵에 입력해 줍니다. 입력하면서 빈칸인지, 바이러스인지 체크하여 따로 좌표를 저장해 줍니다. 빈칸의 용도는 빈칸 중 3개 선택하기에 쓰이며, 바이러스의 용도는 BFS를 위한 큐에 입력해줄 때 사용됩니다.

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 8
#define MAX_M 8
#define VIRUS 2
#define WALL 1
#define EMPTY 0
struct coor
{
	int y;
	int x;
};
int N;
int M;
int originalmap[MAX_N][MAX_M] = { 0, };
vector<coor> virusarr;
vector<coor> emptyarr;
int sol = 0;

int main() {
	cin >> N >> M;
	int temp;
	coor tempcoor;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> temp;
			originalmap[y][x] = temp;
			if (temp == EMPTY) { //빈칸들 모아두기, 조합용
				tempcoor.y = y;
				tempcoor.x = x;
				emptyarr.push_back(tempcoor);				
			} 
			else if (temp == VIRUS) { //바이러스 모으기, 이것들로 BFS시작할 것
				tempcoor.y = y;
				tempcoor.x = x;
				virusarr.push_back(tempcoor);
			}
		}
	}

	//조합으로  총 빈칸 중 3개 뽑기

	cout << sol;
	return 0;
}

위 코딩은 문제없이 작성할 수 있습니다. 문제를 이해하면서 조합, BFS를 사용할 것이라는 걸 알 수 있었고 어디에 어떤 값들이 필요한지 파악한 상태입니다.

2-2) 조합 구현하기

이제 조합 알고리즘을 구현해 봅시다. 기존 조합 알고리즘 포스팅과 동일한 코드를 사용했습니다. 이 문제의 핵심은 BFS에 있습니다.

2021.04.01 - [알고리즘/SW역량테스트] - (4장-2) 조합(Combination) 알고리즘이란?

#define SELECTWALL 3
vector<int> flagComb;
vector<coor> emptyselectarr;

void operation() {
	// 조합 잘 나왔는 지 테스트
	for (int i = 0; i < emptyselectarr.size(); i++) { //항상 3
		cout << emptyselectarr[i].y << ", " << emptyselectarr[i].x << endl;
	}
	cout << endl;

	// 해당 경우에서 사용할 맵 복사 copy();
	// 3개의 벽 세우기 buildwall();
	// 바이러스 확산 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 < emptyarr.size(); i++) {
			if (flagComb[i] == 1) emptyselectarr.push_back(emptyarr[i]);
		}
		operation();
		emptyselectarr.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 < emptyarr.size(); j++) {
				if (flagComb[j] == 1) emptyselectarr.push_back(emptyarr[j]);
			}
			operation();
			emptyselectarr.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 < emptyarr.size(); i++) {
		flagComb.push_back(0);
	}
	//조합으로  총 빈칸 중 3개 뽑기
	comb(emptyarr.size(), SELECTWALL);
	cout << sol;
	return 0;
}

여러 문제를 풀다 보면, 조합에서는 변경될 곳이 거의 없다는 걸 알 수 있습니다. nCr에서 n과 r의 배열만 만들어 주고 r개 선택 시 동작할 함수만 구현하면 조합 문제는 변화가 없습니다. 조합은 매우 쉬운 문제입니다.

우리가 사용할 벽 3개를 구했다면 이 경우에서 사용할 맵을 복사하고, 벽을 세우는 동작이 들어갑니다.

int emptycount = 0;
int copymap[MAX_N][MAX_M] = { 0, };

void copy() {
	emptycount = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			copymap[i][j] = originalmap[i][j];

			if (originalmap[i][j] == EMPTY) emptycount++;			
		}
	}
}
void buildwall() {
	for (int i = 0; i < SELECTWALL; i++) { //항상 3
		copymap[emptyselectarr[i].y][emptyselectarr[i].x] = WALL;	
		emptycount--;
	}
}

copy동작을 하면서 빈칸은 모두 카운팅을 하고 벽을 만들면서 3개는 빼주면 됩니다.

2-3) BFS 구현하기

operation 함수에서 이제 BFS를 시작합니다. BFS 알고리즘과 거의 흡사한 틀을 보이고 있기 때문에 기존 BFS 알고리즘을 확실하게 익혀야 합니다.

2021.03.16 - [알고리즘/SW역량테스트] - (3장-2) BFS(너비우선탐색) 알고리즘이란?

#include <queue>

bool checkmaprange(coor yx) {
	if ((0 <= yx.y && yx.y < N) && (0 <= yx.x && yx.x < M))
		return true;
	return false;
}

void BFS() {
	queue<coor> q;
	for (int i = 0; i < virusarr.size(); i++) { //총 바이러스 수
		q.push(virusarr[i]);		
	}
	coor current;
	coor candidate;
	int dy[4] = { 0,-1,0,1 }; // 순서는 왼,위,오,아
	int dx[4] = { -1,0,1,0 };
	int count = emptycount; // 이번 조합에서 빈칸 카운팅
	while (!q.empty()) {
		current = q.front();
		for (int i = 0; i < MAX_Dir; i++) {
			candidate.y = current.y + dy[i];
			candidate.x = current.x + dx[i];
			if ((copymap[candidate.y][candidate.x] == EMPTY) && checkmaprange(candidate)) { //방문한적 없는 좌표, 
				q.push(candidate);
				copymap[candidate.y][candidate.x] = VIRUS; //바이러스 확산, 방문처리
				count--;
			}
		}
		q.pop();
	}
	if (sol < count) {
		sol = count; // 최대값만 유지
	}
}

위 코드를 보면 기존 BFS알고리즘과 거의 흡사한 것을 알 수 있습니다. 큐를 생성하고, 초기값으로 초기 바이러스를 전부 push 해줍니다. 그리고 저희는 빈칸이면 미방문, 그 외는 방문으로 대체하기 때문에 방문 표시는 별도로 할 필요가 없습니다.

이런 좌표에서는 정점과 이어진 정점은 4방향밖에 없기 때문에 dy, dx를 통해 이어진 정점으로 접근할 수가 있습니다. 이건 2차원 맵 문제에서 자주 쓰이는 방식입니다. 이웃 정점이 빈칸이고 범위를 벗어난 건지 체크하고 큐에 이웃 정점을 추가합니다. 그리고 맵에 바이러스로 표기하여 방문했다는 것을 표기합니다. (빈칸 수도 1 감소)

큐가 없을 때까지 반복하면 while문을 종료합니다. 이는 바이러스 확산이 더 이상 일어날 수 없다는 의미입니다. 이 상태에서 빈칸수 count가 우리가 구하고자 하는 값입니다.

3) 주의 사항

이전에도 설명했지만 백준 문제는 테스트 케이스가 아닌 단일 입력에 대한 문제이기 때문에 초기화를 할 필요가 없습니다. 다만, 삼성 SW 역량테스트에서는 꼭 초기화에 신경 써주세요.

연구소 3과 약간의 차이를 두면서 문제를 풀어봤습니다. BFS에서 조건을 판별할 시 함수로 추출해도 괜찮고 아니어도 괜찮습니다. Isexceed 플래그로 불필요한 계산을 막아도 되고 안 해도 괜찮습니다. 최적화에 좀 더 신경 쓰고 싶으면 하는 걸 추천드립니다.

나머지는 코드에 주석으로 설명하고 있습니다. 혹시 이해 안 되는 부분이 있다면 댓글 주세요.

저작자표시 비영리 변경금지

'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글

[백준 14888번] 연산자 끼워넣기 (순열) (0)	2021.04.16
[백준 14503번] 로봇 청소기 (시뮬레이션) (0)	2021.04.16
[백준 14889번] 스타트와 링크 (조합) (0)	2021.04.14
[백준 15686번] 치킨배달 (조합) (0)	2021.04.08
[백준 17142번] 연구소 3 (조합, BFS) (0)	2021.04.08

나의 디렉토리 이야기

[백준 14502번] 연구소 (조합, BFS)

1) 문제 이해

2) 구조 잡기

3) 주의 사항

'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글

댓글

티스토리툴바

[백준 14502번] 연구소 (조합, BFS)

1) 문제 이해

2) 구조 잡기

3) 주의 사항

'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글

관련글

댓글

티스토리툴바