글 읽기 - 모든 경우를 고려한 것 같은데 틀렸다고 나옵니다.

jjh030116 1년 전 0

기존의 dfs 방식에서 재귀함수 리턴시에 방문 흔적도 모두 지웠고,

노드들이 끊어져 있는 경우도 22번 줄의 for문을 통해 해결했습니다. 또한, 시간초과를 피하고자 visit라는 배열을 새로 선언해 dfs 탐색 시 방문한 적이 한번이라도 있으면 재귀함수에 들어가지 못하도록 하였습니다.

아무리 고민해도 문제점이 무엇인지 잘 보이지 않습니다.

혹시, 문제점이 보이신다면 답변 부탁드리겠습니다.

감사합니다.

#include<algorithm>
#include<iostream>
using namespace std;

void rec(int cur);

int visit[2000];
int arr[2000][2000];
int visited[2000];
int cnt=0;
int N, M;

int main(void){
    cin>>N>>M;
    int p1, p2;
    for(int i=0; i<M; i++){
        cin>>p1>>p2;
        arr[p1][p2]=1;
        arr[p2][p1]=1;
    }

	for(int i=0; i<N-4; i++) {
		if(visit[i]==1) continue;
		cnt=0;
		rec(i);
	}
	
    cout<<"0";
}

void rec(int cur){
    visited[cur]=1;
    visit[cur]=1;
    for(int i=0; i<=N-1; i++){
        if(arr[cur][i]==1 && visited[i]==0){
            cnt++;
            
            if(cnt>=4) {
        	cout<<1;
        	exit(0);
    		}
            rec(i);
        }
    }
	cnt--;
	visited[cur]=0;
	
}

asdarwin03 1년 전 1

코드를 읽어봤는데 0번부터 순서대로 탐색해 나가는게 문제인 것 같습니다.

예를들어 ABCDE가 친구 관계인데 A-B-C-D-E가 각각 1-0-2-3-4 번이면, 문제에서 요구하는 친구관계가 존재함에도 0이 출력됩니다.

4
1
2
3
4
    
Output: 0
Answer: 1

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

문제

문제

출처

ICPC

모든 경우를 고려한 것 같은데 틀렸다고 나옵니다.

jjh030116 1년 전 0

asdarwin03 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말