[백준] 14502 연구소 with C++ (삼성기출)

 

https://www.acmicpc.net/problem/14502

14502번: 연구소

언어: C++, 시간: 52ms

 

 

2차원 격자에서 조합을 이용한 대표적인 문제.

 

사실 조합을 안 쓰고 그냥 순열로 벽을 세우는걸 생각해도 된다. 하지만 그러면 굉장히 느려진다.

(나의 경우 52ms -> 332ms)

 

DFS를 통해서 벽을 세우고, 벽을 다 세우면 BFS를 이용해서 바이러스 퍼뜨렸다.

꼭 복습하기!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int MAP[9][9];
int N, M;
int emptyCnt;
int answer = 0;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

struct Node {
	int y;
	int x;
};
vector <Node> startPoints;

void input() {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> MAP[i][j];
			if (MAP[i][j] == 0)
				emptyCnt++;

			else if (MAP[i][j] == 2) {
				startPoints.push_back({ i, j });
			}
		}
	}

	emptyCnt = emptyCnt - 3;	// 짜피 벽 3개 세울꺼니깐
}

// BFS로 바이러스 퍼뜨리기
void spread() {
	int curEmptyCnt = emptyCnt;
	for (auto startPoint : startPoints) {

		queue <Node> q;
		q.push({ startPoint.y, startPoint.x });

		while (!q.empty()) {
			Node now = q.front();
			q.pop();

			for (int k = 0; k < 4; k++)
			{
				int ny = now.y + dy[k];
				int nx = now.x + dx[k];

				if (ny < 0 || nx < 0 || ny >= N || nx >= M)
					continue;

				if (MAP[ny][nx] != 0)
					continue;

				MAP[ny][nx] = 2;
				curEmptyCnt--;
				q.push({ ny, nx });
			}
		}
	}
	answer = max(answer, curEmptyCnt);
}


void func(int level, int preRow, int preCol) {

	// 종료조건
	if (level == 3) {
		int backupMAP[9][9];
		memcpy(backupMAP, MAP, sizeof(MAP));
		spread();
		memcpy(MAP, backupMAP, sizeof(MAP));
		return;
	}

	// 탐색
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (MAP[i][j] != 0)
				continue;
			
            ///////////////// 아래의 두 if문을 주석처리해도 코드는 잘 돌아간다. 
            // 아래의 문장을 주석처리하면 순열이고, 순열은 조합을 포함하기 때문.
            // 하지만 코딩테스트에 시간초과를 대비하기 위해 꼭 조합 쓰는 방법 익히기!!!
			if (level > 0 && i < preRow)
				continue;

			if (level > 0 && i == preRow && j <= preCol)
				continue;
            //////////////////

			MAP[i][j] = 1;
			func(level + 1, i, j);
			MAP[i][j] = 0;
		}
	}
}

int main() {
	//freopen("sample_input.txt", "r", stdin);
	input();
	func(0, 0, 0);

	cout << answer;

	return 0;
}