글 읽기 - 시간 초과 해결을 못 하겠습니다.

park780172 5년 전 0

계속 시간 초과를 어떻게하면 더 줄일까에 대해 고민을 해봐도
마땅한 방법이 떠오르지 않아 질문 해봅니다.

제가 의도한 문제 풀이는

우선 2중 for문으로 (0, 0)에서 출발하여 Map[행][열]의 값이 0인 곳을 찾은 후
이 값을 1로 바꿔주고 DFS(행, 열) 탐색합니다. 그리고 다시 Map[행][열]의 값을 0으로 원상복구시킵니다.

그리고 ans = max(ans, cnt);를 통해 ans의 값을 갱신 시켜줍니다.

어차피 무조건 단 한 곳만 바꿔서 그 바꾼 곳을 기준으로 최대 크기를 구하는 것이므로,

복잡하게 구현할 필요가 없다고 느꼈습니다.

예제들은 다 맞게 뜹니다.

배열 크기가 최대 1000 * 1000라서 직접 1000 * 1000 배열 시간 초과에 해당하는

반례를 못 찾겠습니다.

그래서, 제 코드에서 어떻게하면 시간 더 줄일 수 있는 방법이 있는지 궁금하여

질문해봅니다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")

using namespace std;

int Map[1001][1001] = { 0, };

int N = 0, M = 0, ans = 0, cnt = 0;

int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };

bool visit[1001][1001] = { false, };

void DFS(int r, int c)
{
	visit[r][c] = true; // 방문 표시

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

		if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x] || Map[y][x] == 0) continue;

		++cnt; // 1 증가
		DFS(y, x);
	}
}

int main(void)
{
	ans = -987654321;

	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &Map[i][j]);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (Map[i][j] == 0)
			{
				memset(visit, false, sizeof(visit)); // 다시 탐색해야하므로, 방문 초기화
				cnt = 1; // 그 위치도 포함
				 
				Map[i][j] = 1; // 1로 바꿔준후

				DFS(i, j); 
				// 그 점부터 시작하여 DFS 실행한다. 
				// 어차피 바꾼 점을 기준으로 최대 크기를 구하는 것이기 때문에 이 점부터 시작하여도 된다.

				Map[i][j] = 0; // 다시 원래대로 0으로 바꿔준다.
				
				ans = max(ans, cnt); // 최댓값 갱신
			}
		}
	}

	printf("%d\n", ans);

	return 0;
}

p_0 5년 전 1

다음과 같은 입력이 시간초과를 일으키는 듯 보입니다.

input :

1000 1000

0 0 0 0 ... ... 0 0 0 0

. .

0 0 0 0 ... ... 0 0 0 0

output : 1

0이 많은 입력의 경우 memset을 그만큼 많이 해주다 보니 시간초과가 나는것 같습니다.

psi0613 5년 전 1

맵 사이즈가 최대 1000*1000이라서 모든 지점을 한 번씩 1로 바꾸면서 그 때마다 DFS를 돌리면 시간초과가 나는게 맞는 거 같아요

저는 전체적으로 한 번 서치해서 각 영역을 찾아 놓고 그 후에 각 점에 대해서 4방을 보면서 이웃한 부분에 영역이 있는지 체크하면서 진행했네요

이게 말인지 뭔진 모르겠는데 도움이 되셨으면 좋겠네요ㅠ

park780172 5년 전 0

@p_0
@psi0613

두 분 모두 감사합니다.

memset이 의외로 시간이 걸리는가 보군요.

엄청 빠른 줄 알았는데..

생각해보니 미리 DFS로 그룹화 시켜서 이것을 저장시켜 활용하는 것이 더 빠를 수 있을 것 같아서

구현하여 제출하였더니 맞았습니다.

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

문제

문제

출처

ICPC

시간 초과 해결을 못 하겠습니다.

park780172 5년 전 0

p_0 5년 전 1

psi0613 5년 전 1

park780172 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말