글 읽기 - 코드 최적화 질문드립니다.

qptnnm 5년 전 0

아래 코드를 짜서 최적화를 하고 있는데... 잘 안 되네요.

질문 게시판에 올라와 있는 코드와 알고리즘은 같은데, 시간치이가 5배 정도 납니다...

어느 부분을 수정해야 최적화를 잘 할 수 있을까요?

고수님들의 조언 부탁드립니다.

#include <stdio.h>
#include <stdbool.h>
#pragma warning(disable: 4996

typedef enum Block
{
	EMPTY = 0,
	WALL = 1,
	VIRUS = 2
};

typedef struct Point
{
	int row;
	int col;
} POINT;

int dr[4] = { -1, 0, 1,  0 };
int dc[4] = {  0, 1, 0, -1 };

int N, M;
int map[10][10];
int map_tmp[10][10];

POINT virus[10];
int Nvirus, Nempty, tmp_res, res;


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

void BFS(int r, int c, int depth)
{
	if (map_tmp[r][c] == EMPTY)
	{
		tmp_res--;
		map_tmp[r][c] = VIRUS;
	}

	for (int i = 0; i < 4; i++)
	{
		if (r + dr[i] >= 0 && r + dr[i] < N 
			&& c + dc[i] >= 0 && c + dc[i] < M 
			&& map_tmp[r + dr[i]][c + dc[i]] == EMPTY)
			BFS(r + dr[i], c + dc[i], depth + 1);
	}
}

void Spread()
{
	tmp_res = Nempty;
	CopyMap();

	for (int i = 0; i < Nvirus; i++)
	{
		POINT tmp = virus[i];
		BFS(tmp.row, tmp.col, 1);
		if (tmp_res == 3 || tmp_res - 3 < res)
			return;
		
	}
	return;
}

int SelectWall(int depth)
{
	// Spread
	if (depth > 3)
	{
		// 벽 3개 세운거 고려
		Spread();
		int tmp = tmp_res - 3;
		if (res < tmp)
			res = tmp;
		return 1;
	}

	// Build Wall
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == EMPTY)
			{
				map[i][j] = WALL;
				SelectWall(depth + 1);
				map[i][j] = EMPTY;
			}
			
		}
	}

}



int main()
{
	// Read N, M
	scanf("%d %d", &N, &M);
	
	// Read Input Map
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%d", &map[i][j]);
			// Add Virus Info
			if (map[i][j] == VIRUS)
			{
				virus[Nvirus].row = i;
				virus[Nvirus++].col = j;
			}
			else if (map[i][j] == EMPTY)
			{
				Nempty++;
			}
		}
	}

	SelectWall(1);
	printf("%d", res);

}

djm03178 5년 전 1

차이가 나는 부분은 이 코드는 SelectWall 함수가 항상 0 0 좌표부터 탐색을 시작하여, 중복된 벽의 조합을 다시 선택하고 있다는 점입니다. 예를 들어 a, b, c라는 세 좌표에 벽을 세운 적이 있다면 b, a, c나 c, b, a 등의 조합은 고려해볼 필요가 없습니다.

Green55 5년 전 1

SelectWall()에서 인자로 i와 j를 넘기는 것을 고려해보세요.

제가 사용한 코드의 일부입니다.

//(x,y)에 벽을 세울지 고려해본다.
void backTracking(int x, int y, int cnt){
	if(cnt == 3){ // 벽 3개를 세울 곳을 전부 정함
		check();
		return;
	}
	if(y==m){ //가로 탐색 끝
		backTracking(x+1, 0, cnt);
		return;
	}
	if(x==n){ //탐색 끝
		return;
	}
	if(board[x][y]){ //벽이 아니면 넘어감
		backTracking(x, y+1, cnt);
		return;
	}
	//여기에 벽을 세워본다.
	board[x][y] = 1;
	backTracking(x, y+1, cnt+1);
	board[x][y] = 0;
	backTracking(x, y+1, cnt);
}

qptnnm 5년 전 0

고수님들의 답변 감사합니다 !

미처 생각하지 못한 부분이었네요. 많이 배워갑니다

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

문제

문제

출처

ICPC

코드 최적화 질문드립니다.

qptnnm 5년 전 0

djm03178 5년 전 1

Green55 5년 전 1

qptnnm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말