글 읽기 - 시간초과 DFS, BFS

sminhyuck 4년 전 0

코드를 다음과 같이 최대한 적게 돌아가도록 줄여봤는데, 어느 부분때문에 시간초과가 발생하는지 잘모르겠습니다.

시간 초과 나지 않게끔 어느 부분을 어떻게 수정하면 나아질지 조언 부탁드립니다!

시간초과는 시작하고 1%에서 초과가 뜹니다 ㅠㅠ

#include <iostream>
#include <queue>
#define EMPTY -2
#define WALL -3
#define VIRUS 2
#define REST -1

using namespace std;
struct pos {
	int y, x, ti;
};
pos V[2500];
queue<pos> oq;

bool USE[2500];
int MAP[50][50]; //  -2이 빈칸, 0이상은 활성바이러스, -1는 비활성 바이러스, -3은 벽
int temp[50][50];
int N, M, VC, T;
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

void init() {
	cin >> N >> M;
	VC = 0; T = 2501; 
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++) {
			int t;
			cin >> t;

			if (t == VIRUS) {
				USE[VC] = false;
				V[VC++] = { y,x,0 };
				MAP[y][x] = REST;
			}
			else if (t == 1) {
				MAP[y][x] = WALL;
			}
			else
				MAP[y][x] = EMPTY;
			temp[y][x] = MAP[y][x];
		}
}

void DFS(int s, int choose);
void spread();
int search();

int main() {
	init();
	//print();
	DFS(0, 0);
	if (T == 2501) T = -1;
	cout << T << endl;
}

void DFS(int s, int choose) {
	if (choose == M) {
		for (int i = 0; i < VC; i++)
			if (USE[i]) oq.push(V[i]);

		spread();

		int t = search();
		if (t != -1)
			if (t < T) T = t;
		return;
	}

	for (int i = s; i < VC; i++) {
		if (!USE[i]) {
			USE[i] = true;
			DFS(i, choose + 1);
			USE[i] = false;
		}
	}
}
// 바이러스가 퍼지는 동작
void spread() {
	queue<pos> q;
	while (!oq.empty()) {
		q.push(oq.front());
		oq.pop();
	}

	while (!q.empty()) {
		int Y = q.front().y;
		int X = q.front().x;
		int t = q.front().ti;

		q.pop();
		if (t >= T) return;
		if (temp[Y][X]== EMPTY || temp[Y][X] > t) temp[Y][X] = t;
		if (temp[Y][X] == REST) temp[Y][X]= WALL;

		for (int i = 0; i < 4; i++) {
			int my = Y + dy[i];
			int mx = X + dx[i];
			if (my >= 0 && my < N && mx >= 0 && mx < N) {
				if (temp[my][mx] == EMPTY || temp[my][mx] > t + 1 || temp[my][mx] == REST) 
					q.push({ my,mx,t + 1 });
				
			}
		}

	}
	
}
// 시간 반환
int search() {
	int MAX = 0;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++) {
			if (temp[y][x] == EMPTY) MAX = -1;
			if (MAX != -1 && temp[y][x] > MAX) MAX = temp[y][x];
			temp[y][x] = MAP[y][x];
		}
	return MAX;
}

seojeongwook2 4년 전 1

일단 불필요한 부분이 조금 있습니다.

oq가 필요없습니다.

굳이 oq에 쌓았다가 q에다가 다시 쌓기보다는 DFS에서 깊이가 증가할 때 마다 배열 하나로 처리하면 oq가 필요없습니다.

for문으로 후보군을 모두 돌아볼 필요없이 골라진 것만 담으면 됩니다.

2. 시간반환하는 2차원 배열을 사용하기 보다는 BFS에서 시간을 체크해주면 됩니다. 그러면 굳이 2중 for문을 계속 돌릴 필요가 없습니다.

oq를 지워본 코드를 부분적으로 작성했습니다.

for (int i = s; i < VC; i++) {
	if (!USE[i]) {
		USE[i] = true;
		PICKED[choose] = i;
        // choose 번째에 무엇을 뽑았는 지 PICKED 1차원 배열에 저장
		DFS(i, choose + 1);
		USE[i] = false;
	}	
}

// Spread에서 q에 넣는 연산
for (int i = 0; i < M; i++) {
	q.push(V[PICKED[i]]);
}

sminhyuck 4년 전 0

답변 감사합니다!

조언해주신대로 수정을 해봤는데 여전히 시간초과가 뜨네요 ㅜㅜ

일단 search 부분은 어차피 맵복원이 필요해서 하는김에 같이 탐색하는 방식으로 최대한 시간을 줄였습니다.

시간초과가 뜨는 부분이 아무래도 확산 부분에서 알고리즘으로 인해 일어나는것 같은데

어떻게 더 가지치기를 하여야하는지 모르겠습니다..

#include <iostream>
#include <queue>
#define EMPTY -2
#define WALL -3
#define VIRUS 2
#define REST -1

using namespace std;
struct pos {
	int y, x, ti;
};
pos V[2500];
bool USE[2500];
int PICKED[10];
int MAP[50][50]; //  -2이 빈칸, 0이상은 활성바이러스, -1는 비활성 바이러스, -3은 벽
int temp[50][50];
int N, M, VC, T;
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

void init() {
	cin >> N >> M;
	VC = 0; T = 2501; 
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++) {
			int t;
			cin >> t;

			if (t == VIRUS) {
				USE[VC] = false;
				V[VC++] = { y,x,0 };
				MAP[y][x] = REST;
			}
			else if (t == 1) {
				MAP[y][x] = WALL;
			}
			else
				MAP[y][x] = EMPTY;
			temp[y][x] = MAP[y][x];
		}
}

void DFS(int s, int choose);
void spread();
int search();

int main() {
	init();
	DFS(0, 0);
	if (T == 2501) T = -1;
	cout << T << endl;
}

void DFS(int s, int choose) {
	if (T == 0) return;

	if (choose == M) { // 확산할 바이러스 선정완료, 확산 및 시간계산
		spread();
		int t = search();
		if (t != -1)
			if (t < T) T = t;
		return;
	}

	for (int i = s; i < VC; i++) {
		if (!USE[i]) {
			USE[i] = true;
			PICKED[choose] = i;
			DFS(i, choose + 1);
			USE[i] = false;
		}
	}
}
// 바이러스가 퍼지는 동작
void spread() {
	queue<pos> q;
	for (int i = 0; i < M; i++)
		q.push(V[PICKED[i]]);

	while (!q.empty()) {
		int Y = q.front().y;
		int X = q.front().x;
		int t = q.front().ti;
		q.pop();

	//	if (t >= T) return;

		if (temp[Y][X] == REST) temp[Y][X]= WALL; // 비활성화 바이러스를 활성화처리, 벽으로 인식해서 재방문 방지
		else if (temp[Y][X] == EMPTY || temp[Y][X] > t) temp[Y][X] = t; // 맵에 시간 마킹
		
		for (int i = 0; i < 4; i++) {
			int my = Y + dy[i];
			int mx = X + dx[i];
			if (my >= 0 && my < N && mx >= 0 && mx < N) {
				if (temp[my][mx] == EMPTY || temp[my][mx] == REST || temp[my][mx] > t + 1) {
					q.push({ my,mx,t + 1 });
					if (t+1 >= T) return; // 현재 시간이 T보다 같거나 크면 더 탐색필요없음
				}
				
			}
		}

	}

}

// 시간 반환 및 맵 복원
int search() {
	int MAX = 0;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++) {
			if (temp[y][x] == EMPTY) MAX = -1;
			else if (MAX != -1 && temp[y][x] > MAX) MAX = temp[y][x];
			temp[y][x] = MAP[y][x];
		}
	return MAX;
}

sminhyuck 4년 전 0

혹시나 해서 89라인 뒤에 else continue;를 추가하여 시간을 단축시키는 경우에는 테스트케이스는 모두 잘 나오나 틀렸습니다가 뜨네요 ㅠㅠ

sminhyuck 4년 전 1

문제 해결했습니다 :)

기존에 88라인 쯤에서 큐에 푸시를 한 값을 꺼내서 맵에 표기가 아니라, 푸시할때 같이 표기를 해주니 가지치기가 되어 잘동작하는것 같습니다! 감사합니다:)

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

문제

문제

출처

ICPC

시간초과 DFS, BFS

sminhyuck 4년 전 0

seojeongwook2 4년 전 1

sminhyuck 4년 전 0

sminhyuck 4년 전 0

sminhyuck 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말