[백준][삼성 SW 역량 테스트][Gold 5][C++] 14502 연구소

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14502 연구소 (Gold 5)

14502번: 연구소

 

---

문제 풀이

접근 방식

이 문제는 벽 3개를 세운 뒤, 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 문제이다.

 

우선, 3중 for문으로 벽 3개를 세운 뒤, DFS 함수를 만들어 바이러스를 퍼뜨려주었다.

(입력 받을 때, 바이러스의 위치를 저장하여 BFS 방식으로 바이러스를 퍼뜨려줘도 된다.)

 

그 후, map에 있는 0의 개수를 세어 안전 영역의 크기를 구해주었다.

이 값을 max값과 비교하여 안전 영역 크기의 최댓값을 구해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> map;

void DFS(int n, int m, int i, int j) {
	if (i + 1 < n && map[i + 1][j] == 0) {
		map[i + 1][j] = 2;
		DFS(n, m, i + 1, j);
	}
	if (j + 1 < m && map[i][j + 1] == 0) {
		map[i][j + 1] = 2;
		DFS(n, m, i, j + 1);
	}
	if (i - 1 >= 0 && map[i - 1][j] == 0) {
		map[i - 1][j] = 2;
		DFS(n, m, i - 1, j);
	}
	if (j - 1 >= 0 && map[i][j - 1] == 0) {
		map[i][j - 1] = 2;
		DFS(n, m, i, j - 1);
	}
}

int main() {
	int n, m;
	cin >> n >> m;
	map.assign(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
    
	vector<vector<int>> copy;
	copy = map;
	int max = 0;
	for (int a = 0; a < n*m; a++) {	// 첫 번째
		if (map[a / m][a % m] != 0) continue; 
		for (int b = a + 1; b < n * m; b++) {	// 두 번째
			if (map[b / m][b % m] != 0) continue;
			for (int c = b + 1; c < n * m; c++) {	// 세 번째
				if (map[c / m][c % m] != 0) continue;
				map[a / m][a % m] = 1;
				map[b / m][b % m] = 1;
				map[c / m][c % m] = 1;

				for (int i = 0; i < n; i++) {	// 2 퍼뜨리기
					for (int j = 0; j < m; j++) {
						if (map[i][j] == 2)
							DFS(n, m, i, j);
					}
				}

				int count = 0;
				for (int i = 0; i < n; i++) {	// 0 개수 세기
					for (int j = 0; j < m; j++) {
						if (map[i][j] == 0)
							count++;
					}
				}

				if (max < count)	// 최대 0 개수 저장
					max = count;

				map = copy;
			}
		}
	}

	cout << max;
}

실행 결과

실행 결과 : 통과 (40ms)