글 읽기 - DFS 시간초과

jinny 4년 전 0

이문제가 DP를 이용해야 하는 문제라고 해서 결국 풀긴 풀었지만 처음에 DFS로 풀었을때 왜 시간초과가 나는지 궁금합니다 ㅠㅠ

각 위치에서 4방향 탐색하면서 재귀를 타는데, 한 위치에서 최대 4방향만 조사하기 때문에

500*500*4 = 1000000 (백만) 번의 연산이 이루어 질것 같은데 왜 시간초과가 나나요??

/*내리막길 --DFS*/
#include <iostream>
using namespace std;

int N, M, answer;
int map[500][500];
bool visit[500][500];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };

void DFS(int r, int c, int height) {
	if (r == N - 1 && c == M - 1) {			//맨 오른쪽 아래 도착(기저조건)
		answer++;
		return;
	}
	for (int d = 0; d < 4; d++) {
		int nr = r + dr[d];
		int nc = c + dc[d];
		if (nr >= 0 && nc >= 0 && nr < N && nc < M) {			//다음 위치가 경계 안에 있고,
			if (!visit[nr][nc] && map[nr][nc] < height) {		//방문하지 않고, 현재 높이보다 더 낮을때
				visit[nr][nc] = 1;
				DFS(nr, nc, map[nr][nc]);
				visit[nr][nc] = 0;
			}
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	visit[0][0] = 1;
	DFS(0, 0, map[0][0]);
	cout << answer << endl;

}

fin 4년 전 3

한번 재귀가 이루어질 때 마다 4번의 탐색이 발생하니깐

연산 횟수는 500*500*4가 아니라

4^(500*500)= 4^250000(4의25만제곱)입니다.

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

문제

문제

출처

ICPC

DFS 시간초과

jinny 4년 전 0

fin 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말