22-04-09-14502-연구소

01.재귀를 이용하여 3개의 벽 세우기

void installWall(int y, int x, int count)
{
	if (count == 3) {
		int safeZone = bfs();
		ret = ret < safeZone ? safeZone : ret;
		return;
	}

	for (int i = y; i < N; i++) {
		for (int j = x; j < M; j++) {
			if (board[i][j] == 0) {
				board[i][j] = 3;//벽세우기
				installWall(i, j + 1, count + 1);
				board[i][j] = 0;
			}
		}
		x = 0;
	}
}

02.바이러스 BFS증식

queue<Data>q;
	int safeZone = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 2) {
				q.push({ i,j,0 });
			}
		}
	}
	int visit[NS][NS] = { 0, };//방문 체크
	while (!q.empty())
	{
		Data c = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			Data n;
			n.y = c.y + dy[dir]; n.x = c.x + dx[dir];
			n.cnt = c.cnt + 1;
			if ((0 <= n.y&&n.y < N && 0 <= n.x&&n.x < M)&&(visit[n.y][n.x]==0&&board[n.y][n.x]==0)) {
				visit[n.y][n.x] = 1;
				q.push(n);
			}
		}
	}

03.안전지역 확인하기

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 0 && visit[i][j] == 0) {
				safeZone++;
			}
		}
	}

04.전체소스

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
#define NS 9
using namespace std;
int N,M,ret;
int board[NS][NS];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
	int y, x, cnt;
};
void init() {
	N = M= 0;
	ret = 0x80000000;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}
int bfs() {
	queue<Data>q;
	int safeZone = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 2) {
				q.push({ i,j,0 });
			}
		}
	}
	int visit[NS][NS] = { 0, };//방문 체크
	while (!q.empty())
	{
		Data c = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			Data n;
			n.y = c.y + dy[dir]; n.x = c.x + dx[dir];
			n.cnt = c.cnt + 1;
			if ((0 <= n.y&&n.y < N && 0 <= n.x&&n.x < M)&&(visit[n.y][n.x]==0&&board[n.y][n.x]==0)) {
				visit[n.y][n.x] = 1;
				q.push(n);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 0 && visit[i][j] == 0) {
				safeZone++;
			}
		}
	}
	
	return safeZone;
}
void installWall(int y, int x, int count)
{
	if (count == 3) {
		int safeZone = bfs();
		ret = ret < safeZone ? safeZone : ret;
		return;
	}

	for (int i = y; i < N; i++) {
		for (int j = x; j < M; j++) {
			if (board[i][j] == 0) {
				board[i][j] = 3;//벽세우기
				installWall(i, j + 1, count + 1);
				board[i][j] = 0;
			}
		}
		x = 0;
	}
}
int main(void)
{
	init();
	installWall(0,0,0);
	printf("%d\n", ret);
	return 0;
}

05.총평

• 위의 문제의 사실 눈 감고도 풀정도로 쉽다.
• 우선 위의 문제는 3가지로 구분을 했음
  • 재귀 이용하기
  • bfs탐색
  • 완전 탐색을 이용하여 영역 확인
• 확실히 그냥 탐색의 경우 문제가 쉬운듯
  • 실수 없었고 그냥 무난하게 풂

https://github.com/3DPIT/study/blob/master/02.studyData/10.Algorithm/2022/%EB%B0%B1%EC%A4%80%EC%BD%94%ED%85%8C/Algorithm/2022/04/0410/22-04-09-14502-%EC%97%B0%EA%B5%AC%EC%86%8C.md

GitHub - 3DPIT/study