글 읽기 - 반례를 못찾겠습니다.

chicchicken7 5년 전 0

게시판에 올라온 반례를 하나하나 다 집어넣어봤지만 모두 결과가 정상적으로 출력되었습니다.

간결한 경우부터 복잡한 경우까지 반례를 넣어봤는데 모르겠네요 ㅠㅠ

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

void DFS(int start, vector<int>* line, bool* check_node);
void BFS(int start, vector<int>* line, bool* check_node);

int main() {
	int N, M, start;	//정점, 간선, 시작점
	vector<int> line[1001];	// 간선연결정보 저장용 벡터
	bool check_node[1001] = { 0, };	//정점을 지나갔는지 확인하는 배열
	check_node[0] = true;

	cin >> N >> M >> start;

	for (int i = 0; i < M; i++) {
		int x, y;

		cin >> x >> y;
		// 양방향 연결 정보 저장
		line[x].push_back(y);
		line[y].push_back(x);
	}
	
	DFS(start, line, check_node);
	cout << endl;
	// 정점 방문 기록 초기화
	for (int i = 1; i < 1001; i++) {
		check_node[i] = false;
	}
	check_node[start] = true;
	BFS(start, line, check_node);
	return 0;
}

void DFS(int start, vector<int>* line, bool* check_node) {
	int min;
	vector<int>::iterator remove_point;

	cout << start << " ";
	check_node[start] = true;
	

	while (!line[start].empty()) {
		bool flag = false;
		min = 1000;
		// 연결된 정점을 모두 방문했다면 돌아감
		for (vector<int>::iterator it = line[start].begin(); it != line[start].end(); it++) {
			if (check_node[*it] == false) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			return;
		}
		for (vector<int>::iterator itr = line[start].begin(); itr != line[start].end(); itr++) {
			if (min > *itr && check_node[*itr] == false) {
				min = *itr;
			}
		}
		DFS(min, line, check_node);
	}
}

void BFS(int start, vector<int>* line, bool* check_node) {
	int min;
	bool flag;
	queue<int> bfs;

	bfs.push(start);

	while (!bfs.empty()) {
		cout << bfs.front() << " ";

		while (true) {
			min = 1000;
			flag = false;

			for (vector<int>::iterator itr = line[bfs.front()].begin(); itr != line[bfs.front()].end(); itr++) {
				if (min > *itr && check_node[*itr] == false) {
					min = *itr;
					flag = true;
				}
			}
			if (!flag) {
				break;
			}
			bfs.push(min);
			check_node[min] = true;
		}

		bfs.pop();
	}
}

djm03178 5년 전 1

1000번 정점만 남았을 때 60, 83번째 줄은 항상 거짓입니다. 남은 정점이 있는데도 flag는 false로 남게 됩니다.

chicchicken7 5년 전 0

정점이 1000일때 플래그를 생각을 못했었네요 ㅠㅠ 감사합니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

chicchicken7 5년 전 0

djm03178 5년 전 1

chicchicken7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말