백준14502번 - 연구소(C++, 삼성 SW 역량 테스트 기출 문제)

 삼성 A형을 목표로 백준 문제풀이를 진행하고 있습니다. 처음 삼성 문제를 풀때 '이렇게 풀어도 되나?' 싶을 정도로 무식하게 구현하다가 제출한 문제에 '맞았습니다'가 뜨는걸 보고 삼성 A형 스타일 문제가 어떤 느낌인지 알게 되었습니다.. 괜히 머리 굴리면서 효율적인 문제풀이 방법을 생각하기 보다는 그냥 있는 그대로 구현하는게 정답이였습니다. 다만 구현이 좀 복잡하기 때문에 main함수에 무식하게 구현하기 보다는, 기능 하나하나를 함수화하여 푸는게 간편하다고 느껴졌습니다. 아래 문제집에서 이제 겨우 4문제를 푼 어린이지만.. 1일 1문제씩 풀어서 2월달에 A형 시험을 꼭 합격해보도록 하겠습니다.

 

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

 

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

int n, m, zCnt=0, mx=-1;
int board[8][8];
int tmpBoard[8][8];
vector<pair<int, int>> zeroPos;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void TmpBoardReset(queue<pair<int, int>>& q) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			tmpBoard[i][j] = board[i][j];
			if (tmpBoard[i][j] == 2) q.push({ i, j });
		}
	}
}

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				zeroPos.push_back({ i, j });
				zCnt++;
			} 
		}
	}
	vector<int> comV(zCnt);
	for (int i = 1; i <= 3; ++i) comV[comV.size() - i] = 1;
	do {
		queue<pair<int, int>> q;
		TmpBoardReset(q);
		for(int i=0; i<zCnt; ++i) if (comV[i] == 1) {
			tmpBoard[zeroPos[i].first][zeroPos[i].second] = 1;
		}
		while (!q.empty()) {
			auto curr = q.front(); q.pop();
			for (int i = 0; i < 4; ++i) {
				int nx = curr.first + dx[i];
				int ny = curr.second + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (tmpBoard[nx][ny] != 0) continue;
				q.push({ nx, ny }); tmpBoard[nx][ny] = 2;
			}
		}
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (tmpBoard[i][j] == 0) cnt++;
			}
		}
		mx = max(mx, cnt);
	} while (next_permutation(comV.begin(), comV.end()));
	std::cout << mx;
}

 

0의 좌표를 pair를 이용해 vector에 저장한 다음, 이중 3개를 선택하는 조합을 구하여 문제를 해결하였습니다.

 

아무리 빡구현 문제더라도 최소한의 성능은 고려해야 겠다고 생각했고, 바이러스를 막기 위해 벽을 설치하는 순서는 상관이 없어서 순열이 아닌 조합으로 구현하여 AC를 받았습니다. (질문 게시판을 보니 순열로 구현시 TLE가 뜬다고 합니다) 조합을 구하는 방법은 0의 좌표를 가진 vector의 length 만큼의 길이를 가진 수열의 뒷부분에 1을 3개를 넣고 순열을 구하는 식으로 구현하였습니다.

 

이런식으로 조합을 구하면 0의 위치에 벽을 세우는 모든 경우의 수를 알 수 있고, 해당 위치에 벽을 세웠을 때 안전지대의 갯수들을 모아 최대값을 구하면 해당 문제를 해결할 수 있습니다.

 

 

 

14502번: 연구소