[C] 백준 14502번 연구소

 

안녕하세요 (ツ) ㅎㅎ

오랜만에(ㅠㅠ) 삼성 SW 역량 테스트 기출문제를 풀어보았습니다 ^____^..

 

백준 14502번

www.acmicpc.net/problem/14502

14502번: 연구소

 

문제에서 주어진 과정은 아래와 같습니다.

1. 벽을 3개 세우기

2. 바이러스 퍼지게 하기

3. 안전 영역 크기 구하기 (+최대 영역 크기 업데이트)

따라서 저는 해당 과정에 맞게 문제를 잘게 쪼개어 보았습니다.

 

1. 벽을 3개 세우기

벽을 3개 세우기 위해서는 빈칸(0)으로 이루어진 공간 중 3개를 임의로 뽑아야 합니다.

해당 문제의 경우에는 주어진 N과 M이 매우 작기 때문에 (3 이상 8 이하)

브루트포스를 활용해서 풀면 좋을 것 같다는 생각이 들었습니다.

따라서 3중 for문을 사용하여 0으로만 이루어진 공간을 3개씩 선정하였습니다.

 

2. 바이러스 퍼지게 하기

벽을 모두 세운 이후에는 바이러스를 상, 하, 좌, 우로 이동해가며 바이러스를 퍼지도록 합니다.

바이러스의 경우에는 벽을 만나지 않는다면 계속해서 퍼져나간다는 성질이 있기 때문에

DFS를 활용하여 바이러스가 퍼져나간 곳이 빈칸(0)이라면 더 퍼져나갈 수 있도록 설정하였습니다.

저는 별도의 스택 배열을 구현하진 않았고, 재귀 함수를 사용하였습니다.

추가로 visited 배열을 사용하여 해당 칸의 방문 여부를 체크해주었습니다.

(중복 탐색 방지)

 

3. 안전 영역 크기 구하기 (+최대 영역 크기 업데이트)

1번 과정을 반복하면서 2번 과정을 수행한 이후, 안전 영역의 크기를 count 해줍니다.

안전 영역은 빈칸을 의미하기 때문에 단순히 for 문으로 배열을 탐색하면서 0의 개수를 count 하였습니다.

그리고 해당 숫자가 현재 최대 영역의 크기보다 크다면 최대 영역 값을 업데이트하였습니다.

 

이를 바탕으로 작성한 코드는 아래와 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int max = 0;
int cnt = 0;

void initialize(int N, int M, int** visited) {
	for (int i = 0; i <= N + 1; i++)
		for (int j = 0; j <= M + 1; j++){
			visited[i][j] = 0;
		}
}

void safe_check(int N, int M, int** map, int** visited) {

	int count = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (map[i][j] == 0 && visited[i][j] != 1)
				count++;

	if (count > max) 
		max = count;
}

void virus_spread(int i, int j, int N, int M, int** map, int** visited) {
	if (i == 0 || j == 0 || i > N || j > M)
		return;

	visited[i][j] = 1;

	// top
	if (map[i - 1][j] == 0 && visited[i - 1][j] == 0)
		virus_spread(i - 1, j, N, M, map, visited);
	// bottom
	if (map[i + 1][j] == 0 && visited[i + 1][j] == 0)
		virus_spread(i + 1, j, N, M, map, visited);
	// left
	if (map[i][j - 1] == 0 && visited[i][j - 1] == 0)
		virus_spread(i, j - 1, N, M, map, visited);
	// right
	if (map[i][j + 1] == 0 && visited[i][j + 1] == 0)
		virus_spread(i, j + 1, N, M, map, visited);

}
void virus(int N, int M, int** map, int** visited) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			if (map[i][j] == 2)
				virus_spread(i, j, N, M, map, visited);
}

void make_wall(int N, int M, int** map, int** visited) {

	for (int i = 1; i <= N * M - 2; i++) {
		if (map[(i - 1) / M + 1][(i - 1) % M + 1] != 0)
			continue;
		map[(i - 1) / M + 1][(i - 1) % M + 1] = 1;
		for (int j = i + 1; j <= N * M - 1; j++) {
			if (map[(j - 1) / M + 1][(j - 1) % M + 1] != 0)
				continue;
			map[(j - 1) / M + 1][(j - 1) % M + 1] = 1;
			for (int k = j + 1; k <= N * M; k++) {
				if (map[(k - 1) / M + 1][(k - 1) % M + 1] != 0)
					continue;
				map[(k - 1) / M + 1][(k - 1) % M + 1] = 1;
				initialize(N, M, visited);
				virus(N, M, map, visited);
				safe_check(N, M, map, visited);
				map[(k - 1) / M + 1][(k - 1) % M + 1] = 0;
			}
			map[(j - 1) / M + 1][(j - 1) % M + 1] = 0;
		}
		map[(i - 1) / M + 1][(i - 1) % M + 1] = 0;
	}

}

int main() {
	
	int N, M;
	scanf("%d%d", &N, &M);

	int** map = (int**)malloc(sizeof(int*) * (N + 2));
	int** visited = (int**)malloc(sizeof(int*) * (N + 2));
	for (int i = 0; i < N + 2; i++) {
		map[i] = (int*)malloc(sizeof(int) * (M + 2));
		visited[i] = (int*)malloc(sizeof(int) * (M + 2));
	}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			scanf("%d", &map[i][j]);

	make_wall(N, M, map, visited);

	printf("%d", max);

	free(map);
	free(visited);

	return 0;

}

 

제가 사용한 함수는 다음과 같습니다!

 

make_wall 함수 → 3개의 벽 선정 (1. 벽을 3개 세우기)

virus, virus_spread 함수 → 바이러스 퍼뜨리기 (2. 바이러스 퍼지게 하기)

safe_check 함수 → 안전 영역 크기 구하기 (3. 안전 영역 크기 구하기 (+최대 영역 크기 업데이트))

initialize → visited 배열 초기화 (벽을 선정할 때마다 초기화해줌)

 

최종적으로 구해야 하는 값은 전역 변수로 선언한 max 값입니다!

 

이 문제는 주어진 입력 값이 크지 않고 문제 자체가 복잡하지 않아서 쉽게 해결할 수 있습니다!

저의 경우에는 배열을 1부터 입력받다 보니깐,,,

make_wall 함수에서 index를 잘못 세주는 문제가 발생하여 ㅠ

오류를 찾는데 허송세월을 보냈답니다..^^*

(배열의 index를 계산하는 코드가 너무 더러워서 매우 불편하네요ㅠ)