[코드트리] 방화벽 설치하기 (삼성 SW 역량테스트 2017 상반기 오후 2번)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/firewall-installation

이후 설명 및 입/출력은 링크 참고

 

방화벽 설치하기 문제 풀이는 BOJ 14502 : 연구소와 같다.

#include <stdio.h>

#define MAX (15)

int T;
int N, M;
int MAP[MAX][MAX];
int tmpMAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX*MAX];
int wp, rp;

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			MAP[r][c] = 0;

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= M + 1; c++)
			MAP[r][c] = 1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);
}

void output()
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS(int r, int c)
{
	wp = rp = 0;

	queue[wp].r = r;
	queue[wp++].c = c;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];
		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (tmpMAP[nr][nc] == 0)
			{
				tmpMAP[nr][nc] = 2;
				queue[wp].r = nr;
				queue[wp++].c = nc;
			}
		}
	}
}

void ALLBFS()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			if (tmpMAP[r][c] == 2) BFS(r, c);
}

int countFire()
{
	int sum = 0;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			sum += !tmpMAP[r][c];

	return sum;
}

int max = 0;
void DFS(int L, int sr)
{
	int tmp;
	if (L > 3)
	{
		for (int r = 0; r <= N + 1; r++)
			for (int c = 0; c <= M + 1; c++)
				tmpMAP[r][c] = MAP[r][c];

		ALLBFS();
		tmp = countFire();

		if (tmp > max) max = tmp;
		return;
	}

	for (int r = sr; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
		{
			if (MAP[r][c] != 0) continue;

			MAP[r][c] = 1;
			DFS(L + 1, r);
			MAP[r][c] = 0;
		}
	}
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		DFS(1, 1);

		printf("%d\n", max);
	}

	return 0;
}