글 읽기 - 왜 시간초과가 날까요 ㅠ

jiwondh 6년 전 0

왜 시간초과가 날까요 ㅠㅠ

제발 알려주세요!!

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <stack>
#include <functional>
#include <math.h>
#include <bitset>

using namespace std;

int N, M;

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

bool isOutSide(pair<int, int> here) {
	int hereY = here.first;
	int hereX = here.second;

	if (hereY < 0 || hereY > N - 1 || hereX < 0 || hereX > M - 1)
		return true;
	else
		return false;
}

int DFS(vector<vector<int> > paper, vector<vector<bool> > visited,
		pair<int, int> here, int cnt) {

	int hereY = here.first;
	int hereX = here.second;
	int herePoint = paper[hereY][hereX];

	visited[hereY][hereX] = true;

	if (cnt == 4) {
		return herePoint;
	}

	int max = 0;

	for (int i = 0; i < 4; i++) {

		int thereY = hereY + dy[i];
		int thereX = hereX + dx[i];
		pair<int, int> there = make_pair(thereY, thereX);

		if (!isOutSide(there) && !visited[thereY][thereX]) {

			int temp = DFS(paper, visited, there, cnt + 1);
			if (max < temp)
				max = temp;
		}
	}
	return max + herePoint;
}

bool isPossible(pair<int, int> here, int i) {
	int hereY = here.first;
	int hereX = here.second;

	switch (i) {
	case 0:
		if (hereY == N - 1 || hereX == 0 || hereX == M - 1)
			return false;
		else
			return true;
	case 1:
		if (hereY == 0 || hereX == 0 || hereX == M - 1)
			return false;
		else
			return true;
	case 2:
		if (hereX == M - 1 || hereY == 0 || hereY == N - 1)
			return false;
		else
			return true;
	case 3:
		if (hereX == 0 || hereY == 0 || hereY == N - 1)
			return false;
		else
			return true;
	default:
		return true;
	}
}
int ReturnSum(vector<vector<int> > paper, pair<int, int> here, int i) {
	int hereY = here.first;
	int hereX = here.second;

	switch (i) {
	case 0:
		return paper[hereY][hereX - 1] + paper[hereY][hereX + 1]
				+ paper[hereY + 1][hereX];
	case 1:
		return paper[hereY][hereX - 1] + paper[hereY][hereX + 1]
				+ paper[hereY - 1][hereX];
	case 2:
		return paper[hereY - 1][hereX] + paper[hereY + 1][hereX]
				+ paper[hereY][hereX + 1];
	case 3:
		return paper[hereY - 1][hereX] + paper[hereY + 1][hereX]
				+ paper[hereY][hereX - 1];
	default:
		return 0;
	}
}
int BFS(vector<vector<int> > paper, pair<int, int> here) {

	int hereY = here.first;
	int hereX = here.second;
	int herePoint = paper[hereY][hereX];

	int max = 0;
	for (int i = 0; i < 4; i++) {
		if (!isPossible(here, i))
			continue;
		int sum = herePoint + ReturnSum(paper, here, i);
		if (max < sum)
			max = sum;
	}
	return max;
}
int main() {

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

	vector<vector<int> > paper(N, vector<int>(M, 0));

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

	vector<vector<bool> > visited(N, vector<bool>(M, false));
	vector<vector<bool> > discovered(N, vector<bool>(M, false));

	int max = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int temp = DFS(paper, visited, make_pair(i, j), 1);
			int temp2 = 0;
			temp2 = BFS(paper, make_pair(i, j));

			if (max < temp)
				max = temp;
			if (max < temp2)
				max = temp2;
		}
	}
	printf("%d", max);

	return 0;
}

hojun2616 6년 전 0

paper 벡터를 전역변수로 선언해보세요 저도 그렇게 해결했습니다.

jiwondh 6년 전 0

전역변수로 바꿨는데도 시간초과가 나네용 ㅠ..

mrchoi90 6년 전 0

정의하신 함수에서 컨테이너(vector, pair)를 입력인자를 복사가 아닌 참조(&)로 전달해보세요.

(예시) vector<vector<int> > paper --> vector<vector<int> >& paper

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

문제

문제

출처

ICPC

왜 시간초과가 날까요 ㅠ

jiwondh 6년 전 0

hojun2616 6년 전 0

jiwondh 6년 전 0

mrchoi90 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말