글 읽기 - 반례를 못찾겠습니다.. 뭐가 잘못인걸까요

rhdtka21 5년 전 0

DFS를 모든 정점에 대해서 반복 수행하는게 잘못된 방법인가요?

#include <iostream>
#include <cstring>
using namespace std;
int N;
int d[101][101];
int check[101];

void DFS(int now, int start){				//현재정점, 시작정점 
	check[now] = 1;							//현재정점 방문 표시  
	for(int i=1; i<=N; i++){
		int next;
		if(d[now][i] == 1){					//현재 정점에 연결된 다음정점 
			next = i;
			if(check[next] != 1)			//방문하지 않았다면 
				DFS(next, start);			//DFS 재귀, 시작정점 유지 
			else if(next == start){			//만약 다음방문이 시작점이면 
				check[start] = -1;			//cycle임을 표시 
			}
		}
	}
}

int main(void){

	cin >> N;
	for(int i=1; i<=N; i++){				//인접 행렬 저장 
		for(int j=1; j<=N; j++){
			cin >> d[i][j];
		}
	}
	
	for(int i=1; i<=N; i++){
		memset(check, 0, sizeof(check));	//DFS하기전 초기화 
		DFS(i, i);
		for(int j=1; j<=N; j++){
			if(j == i){
				if(check[j] == -1){			//사이클이었으면 자기자신 방문가능 
					cout<<"1 ";
				}
				else if(check[j] == 1){		//사이클이 아니었으면 방문불가 
					cout<<"0 ";
				}
			}
			else
				cout<<check[j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

rhdtka21 5년 전 0

모든 정점이 양방향으로 연결되어 있는 경우 -1로 표시했던 cycle이 다시 1이 되는 문제점 있네요.

수정했더니 맞았습니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.. 뭐가 잘못인걸까요

rhdtka21 5년 전 0

rhdtka21 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말