글 읽기 - visited[cur] = false; 꼭 들어가야 하는 이유를 알고 싶습니다.

leehdhj33 5년 전 1

visited[cur] = false; 이부분이 없으면 틀린 이유를 잘 모르겠습니다. 저부분이 없어도 제가 임의로 만들어본 테케도 다 돌아가는데 혹시 저게 없기 때문에 틀린 테스트 케이스 하나만 알려주시고 저부분이 없으면 틀린이유를 설명해 주시면 감사하겠습니다. 부족하지만 열심히 배우겠습니다.

#include<iostream>
#include<vector>
#include<memory.h>
using namespace std;
#define MAXX 2001

vector<int> arr[MAXX];
int N, M,ans;
bool visited[MAXX];

void friend_check(int cur,int cnt) {
	if (cnt == 4) {
		ans=1;
		return;
	}
	//cout << cnt << endl;
	visited[cur] = true;
		for (int i = 0; i < arr[cur].size(); i++) {
			int next=arr[cur][i];
			if (visited[next]==false) {
				friend_check(next, cnt + 1);
			}
			if (ans == 1) return;
		}
		visited[cur] = false;//이거 없으면 안되는 이유
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	for (int i = 0; i < N; i++) {
		memset(visited, false, sizeof(visited));
		friend_check(i, 0);
		if (ans == 1) {
			break;
		}
	}
	if (ans == false) {
		cout << "0";
	}
	if (ans == 1)
		cout << "1";
}//main

djm03178 5년 전 13

다음과 같은 입력에서 틀리게 됩니다.

5
2
4
3
4
5

정답: 1
출력: 0

leehdhj33 5년 전 0

감사합니다 열심히 공부하겠습니다.

kmh03214 4년 전 3

시작이 무조건 0부터 아닌가요?

djm03178 4년 전 0

그러네요. 입력을 잘못 만든 것 같습니다.

kmh03214 4년 전 0

그래도 반례의 의미는 변하지 않아서 감사합니다

huozuyinshua 3년 전 0

찍어보면

0 1 3 2

reset2

reset4

reset3

2 3 4 1

발자국을 지워서 분기노드에서 다시 시도할수 있는것 같다. 노트에 그려보고 뇌내시뮬 돌리면 되는 같음

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

문제

문제

출처

ICPC

visited[cur] = false; 꼭 들어가야 하는 이유를 알고 싶습니다.

leehdhj33 5년 전 1

djm03178 5년 전 13

leehdhj33 5년 전 0

kmh03214 4년 전 3

djm03178 4년 전 0

kmh03214 4년 전 0

huozuyinshua 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말