글 읽기 - 1103 게임 시간초과가... DP를 한다고해서했는데도 7프로에서 시간초과네용..

gktgnjftm 6년 전 0

ㅜㅜㅜ 왜 시간초과일까용..

#include <stdio.h>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;
int Cnt[51][51];
char board[51][51];
bool visited[51][51];
int gox[4] = { 0,1,-1,0 };
int goy[4] = {1,0,0,-1};
bool check;
int dp[51][51];
int dfs(int x, int y,int cnt){
	if (visited[x][y]) {
		check = true;
		return -1;
	}
	visited[x][y] = true;
	for (int i = 0; i < 4; i++){
		int here = board[x][y] - '0';
		int nx = x + here*gox[i];
		int ny = y + here*goy[i];
		if (nx<1 || nx>n || ny<1 || ny>m || board[nx][ny]=='H') continue;
		if (dfs(nx, ny, cnt + 1) == -1) return -1;
	}
	visited[x][y] = false;
	return 1;
}
int go(int x,int y){
	if (x<1 || x>n || y<1 || y>m || board[x][y] == 'H') return 0;
	int &ret = dp[x][y];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = 0; i < 4; i++) {
		int gogo = board[x][y] - '0';
		int nx2 = x + gogo*gox[i];
		int ny2 = y+ gogo*goy[i];
		ret = max(go(nx2, ny2) + 1, ret);
	}
	return ret;
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &board[i][j]);
		}
	}
	memset(dp, -1, sizeof(dp));
	if(dfs(1,1,1)==-1)printf("-1\n");
	else{
		int ans=go(1,1);
		printf("%d\n", ans);
	}
	return 0;
}

cgy7096 6년 전 4

사이클 확인할 때 시간 초과가 나오네요.

visited 처리하고 DFS 동작 후 다시 unvisited로 처리하면, 모든 정점에서 모든 경우를 다 계산하게 돼죠. 이 과정에서 중복이 생기게 되서, 시간초과가 나와요.

어떤 경로에 이미 사이클이 없다는 것을 확인했다면, 그 경로는 앞으로 확인할 필요가 없겠죠.

finished 처리를 통해, 이 경로는 사이클이 없다는 것을 표시해주면 해결될 겁니다.

DFS 사이클 확인 방법 찾아보시면 됍니다!

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

문제

문제

출처

ICPC

1103 게임 시간초과가... DP를 한다고해서했는데도 7프로에서 시간초과네용..

gktgnjftm 6년 전 0

cgy7096 6년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말