글 읽기 - c++ dfsbfs 출력초과

yulgokyeeyee2 2년 전 0

예제 다 돌려 봐도 맞게 나오고 설마해서 뛰어쓰기랑 엔터 다른 글자로 치환해서 출력 해봐도 어디서 잘못 된건지 모르겠네요

#include <iostream>

int a, b, c, x, y;
using namespace std;
int d[1005][1005] = { 0 };
int dd[1005][1005] = { 0 };
int e[1005] = { 0 };
void dfs(int c,int a) {
	for (int i = 0; i < a; i++) {
		if (d[c][i] == 1) {
			if (e[i] == 0) {
				e[i] = 1;
				cout  << " "<< i+1;
			} 
			d[c][i] = 0;
			d[i][c] = 0;
			dfs(i, a); 
		}
	}
}

void bfs(int e[1005]) {
	int fs[1005] = { 0 };
	for (int i = 0; i < a; i++) {
		fs[i] = e[i];
	}
	for (int k = 0; k < a; k++) {
		if (e[k] == 1) {
			for (int i = 0; i < a; i++) {
				if (dd[k][i] == 1) {
					if (e[i] == 0) {
						fs[i] = 1;
						cout << " " << i + 1;
					}
					
				}
			}
			fs[k] == 2;
		}
	}
	for (int i = 0; i < a; i++) {
		e[i] = fs[i];
	}
	int asdf = 0;
	for (int i = 0; i < a; i++) {
		if (e[i] == 1) {
			for (int k = 0; k < a; k++) {
				if (dd[i][k] == 1) {
					if (e[k] == 0) {
						asdf = 1;
					}
				}
			}
		}
	}
	if(asdf == 1) bfs(e);
}

int main() {
	cin >> a >> b >> c;
	c--;
	for (int i = 0; i < b; i++) {
		cin >> x >> y;
		d[x-1][y-1] = 1;
		d[y-1][x-1] = 1;
		dd[x - 1][y - 1] = 1;
		dd[y - 1][x - 1] = 1;
	}
	cout << c+1;
	e[c] = 1;
	dfs( c, a);
	for (int i = 0; i < a; i++) {
		e[i] = 0;
	}
	e[c] = 1;
	cout << "\n" << c+1;
	bfs(e);
}

euphoric_n 2년 전 0

DFS, BFS 함수의 구현이 모두 잘못되었습니다.

BFS는 재귀적으로 동작하지 않으며, 방문 위치를 체크해야 합니다.

구현하신 bfs 함수에서 방문한 지점을 다시 방문하고 있습니다.

DFS 함수의 경우 방문 체크가 제대로 이뤄지지 않고 있습니다.

현재 위치가 이미 방문한 지점인 경우 더 이상 DFS를 진행하면 안됩니다.

yulgokyeeyee2 2년 전 0

bfs가 잘못 작동 중이였네요 큐써서 푸니 해결 됬습니다

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

문제

문제

출처

ICPC

c++ dfsbfs 출력초과

yulgokyeeyee2 2년 전 0

euphoric_n 2년 전 0

yulgokyeeyee2 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말