글 읽기 - c++ 시간초과 질문드립니다.

celestial 3년 전 0

코드는 다음과 같은데..depth가 4일 경우 종료를 해주고

쓸데없는 탐색을 하지 않도록 하였습니다.

그런데 문제는 만일

0부터 N까지 dfs가 돌텐데

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

DFS(i);

}

에서 맨 마지막에 정답이 나오는 케이스가 있기 때문에 시간초과가 나는 것인지 궁금합니다.

dfs 구조 자체의 문제가 있을 수도 있겠찌만...ㅜㅜ

도와주시면 정말 감사합니다!!

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#define MAX 2001
using namespace std;


int N, M;
int depth = 0;
int flag = 0;
vector<int> fr[MAX];
bool visited[MAX];

void DFS(int start) {

	if (depth == 4) {
		flag = 1;
		return;
	}

	for (int i = 0; i < fr[start].size(); i++) {

		if (!visited[fr[start][i]]) {
			visited[fr[start][i]] = true;
			depth++;
			/*printf("DFS(%d)", fr[start][i]);
			printf("current depth : %d\n\n", depth);*/
			DFS(fr[start][i]);
			visited[fr[start][i]] = false;
			depth--;


		}



	}


}



int main() {


	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int snode, tnode;

		cin >> snode >> tnode;
		fr[snode].push_back(tnode);
		fr[tnode].push_back(snode);
	}

	for (int i = 0; i < N; i++) {
		visited[i] = true;
		//printf("DFS(%d)\n\n", i);
		DFS(i);

		for (int i = 0; i < N; i++) {
			visited[i] = false;
		}

		if (depth == 4) {
			flag = 1;
			break;
		}
		depth = 0;


	}

	if (flag == 1) {
		printf("1");
	}
	else {
		printf("0");
	}



}

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

문제

문제

출처

ICPC

c++ 시간초과 질문드립니다.

celestial 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말