글 읽기 - dp를 사용하지 않을 경우의 시간 복잡도가 궁금합니다.

leejuy1140 5년 전 0

dp를 사용할 경우, 한 좌표당 한번씩만 계산하게 되므로, O(nm)이 나오는 것은 알겠습니다.

저는 처음에 dp를 사용하지 않고 그냥 재귀함수로 풀어서 시간초과가 났었습니다.

제가 생각하기로 재귀함수로 짤 경우 시간 복잡도는 크게 봐도 O(n^2*m^2)인 것 같은데,

보드판의 최대 크기가 50이므로, 50^4 = 6250000번의 연산이 나오므로 2초 안에 해결 가능한 것이라고 생각했습니다.

시간 복잡도 계산이 잘못된것 같은데, 재귀함수로 짠 경우의 시간 복잡도를 알려주셨으면 합니다.

아래 코드가 재귀함수로 작성한 코드입니다.

#include <stdio.h>

const int MAX = 51;

int n, m, answer;
char board[MAX][MAX];
bool visited[MAX][MAX];

void game(int r, int c, int cnt)
{
	if (answer == -1) return;
	if (board[r][c] == 'H' || r < 0 || c < 0 || r >= n || c >= m)
	{
		answer = answer > cnt ? answer : cnt;
		return;
	}
	if (visited[r][c])
	{
		answer = -1;
		return;
	}

	visited[r][c] = 1;

	int move = board[r][c] - '0';
	for (int i = 0; i < 4; i++)
	{
		int nr = r, nc = c;
		if		(i == 0) nr += move;
		else if (i == 1) nr -= move;
		else if (i == 2) nc += move;
		else			 nc -= move;
		
		game(nr, nc, cnt + 1);
		if(nr >= 0 && nc >= 0 && nr < n && nc < m)
			visited[nr][nc] = 0;
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		getchar();
		for (int j = 0; j < m; j++)
			scanf("%1c", &board[i][j]);
	}
	
	game(0, 0, 0);
	printf("%d", answer);

	return 0;
}

djm03178 5년 전 1

정확하게 계산하기는 어렵지만 상한은 대략 다음과 같이 생각해볼 수 있습니다.

매 차례마다 움직일 수 있는 칸이 최대 4*9=36칸이고, 이런 움직임을 최대 NM번 할 수 있으니, O(36^(NM)) 정도가 되겠네요.

하지만 실제로는 밖으로 나가지 못하거나, 이미 방문한 칸을 가면 끝나는 등 여러 요소가 있어 이보다는 훨씬 작지만, 전체적으로 지수 형태의 복잡도는 유지됩니다.

leejuy1140 5년 전 0

아 그런식으로 계산해야 하는군요,

감사합니다!

superahn 4년 전 0

윗분 설명에서 한 가지만 정정하자면, 무조건 칸에 써져있는 숫자만큼 이동하는 것이므로, 한 위치에서는 4개 방향이라는 선택지만 있습니다.

최악의 경우를 고려해보면 모든 숫자가 1일 때겠죠.

그러므로 시간복잡도는 O(4^(N*M)) 이 됩니다.

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

문제

문제

출처

ICPC

dp를 사용하지 않을 경우의 시간 복잡도가 궁금합니다.

leejuy1140 5년 전 0

djm03178 5년 전 1

leejuy1140 5년 전 0

superahn 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말