글 읽기 - 코드를 좀 더 최적화하고싶어요

pyd6119 4년 전 0

정답을 받긴 받았으나 정답을 받은 사람들과 비교하여 시간이 오래 걸리는 편인거 같습니다

DFS부분은 브루트포스를 해야 하므로 손댈 부분이 없을 것 같고

BFS부분 반복문에서 시간을 잡아먹는 것 같은데

쓸데없는 부분이 어떤 지점인지 봐주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <queue>

#define MAX 8 + 1

using namespace std;

int N, M;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };
int map[MAX][MAX];
int tempMap[MAX][MAX];
bool visit[MAX][MAX];
int result = -1;
int num;

void copy()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = map[i][j];
}

void BFS() // 2. 바이러스 침투
{
	num = 0; // 각 케이스 당 남은 안전 영역 개수
	copy(); // 여러 케이스들을 테스트해봐야 하기 때문에 임시배열에 값 복사
	queue<pair<int, int>> Q;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (tempMap[i][j] == 2) // 바이러스들 queue에 push
				Q.push({ i, j });
		}

	while (!Q.empty())
	{

		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();

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

			if (0 <= ny && ny < N && 0 <= nx && nx < M)
			{
				if (tempMap[ny][nx] == 0)
				{
					tempMap[ny][nx] = 2;
					Q.push({ ny, nx });
				}
			}
		}
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (tempMap[i][j] == 0)
				num += 1;
		}
		
	result = max(result, num); // 케이스별로 값 비교
}

void DFS(int cnt)
{
	if (cnt == 3) // 벽을 3개 세웠으면
	{
		BFS();
		return;
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 0) 
			{
				map[i][j] = 1;
				DFS(cnt + 1);
				map[i][j] = 0;
			}
		}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
		}

	
	DFS(0); // 1. 벽을 3개 쌓기

	cout << result;
	return 0;
}

djm03178 4년 전 1

DFS야 말로 최적화를 크게 할 수 있는 부분입니다.

벽을 세우는 순서가 상관 없으니, 마지막으로 세운 벽의 위치를 기억해서 그 이후에만 벽을 세워보면 중복된 조합을 탐색하지 않을 수 있습니다.

pyd6119 4년 전 0

DFS 함수에서 이중 for문을 없애고 DFS(y, x, cnt) 로 바꾸어 탐색을 재귀로 바꾸어

중복된 조합들을 없앴습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드를 좀 더 최적화하고싶어요

pyd6119 4년 전 0

djm03178 4년 전 1

pyd6119 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말