글 읽기 - DFS와 BFS, 20%에서 구현이 틀렸습니다.

hdnua 6년 전 11

6페이지까지 있는 모든 반례를 테스트해보았는데, 모두 제대로 나오는 것 같습니다.

어떤 부분이 틀렸을지 궁금합니다.

문제를 맞추기 전까지 제가 테스트했던 반례를 모아보는 것이 의미 있을 것이라 생각하여 올립니다.

혹시 이를 원하지 않는다면 삭제하겠습니다.

※ 지금까지 올라온 모든 반례를 모은 게시물이 아닙니다.

6 5 6
5 4
4 6
2 3
3 1
1 6
----
6 1 3 2 4 5
6 1 4 3 5 2

> BFS의 개념을 잘못 이해하여 "6 1 4 3 2 5"의 출력이 나오는 코드를 작성함. 현재는 수정됨.

15 14 1
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
4 11
4 12
6 13
9 14
9 15
----
1 2 5 6 13 3 7 8 9 14 15 4 10 11 12 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

8 10 1
1 2
1 3
2 4 
2 5 
4 8 
5 8 
3 6 
3 7 
6 8 
7 8
----
1 2 4 8 5 6 3 7 
1 2 3 4 5 6 7 8

6 8 1
1 6 
6 2 
2 4 
4 3 
3 5 
5 1 
5 6 
2 3
----
1 5 3 2 4 6 
1 5 6 3 2 4

7 6 1
1 4
1 3
1 2
4 6
4 5
2 7
----
1 2 7 3 4 5 6 
1 2 3 4 7 5 6

#include <iostream>
#include <vector>
#include <queue>
constexpr char newline = '\n';

// 
constexpr int MAX_VERTEX_CNT = 1000;
constexpr int LINKED = 1;
int _board[MAX_VERTEX_CNT + 1][MAX_VERTEX_CNT + 1];
void link(int v1, int v2) {
	_board[v1][v2] = LINKED;
	_board[v2][v1] = LINKED;
}

// 깊이 우선 탐색: 탐색된 정점의 가장 가까운 자식에 대해 계속해서 탐색을 진행합니다.
void dfs(int v, std::vector<bool> &visited, std::vector<int> &out_list) {
	if (visited[v] == false) {
		out_list.push_back(v);
		visited[v] = true;

		// 값이 작은 정점 순으로 방문합니다.
		for (int i = 0; i < MAX_VERTEX_CNT; ++i) {
			if (_board[v][i] == LINKED && visited[i] == false) {
				dfs(i, visited, out_list);
			}
		}
	}
}
// 너비 우선 탐색: 탐색된 정점의 인접한 노드부터 몽땅 큐로 넣는다
void bfs(int v, std::vector<bool> &discovered, std::queue<int> &remains, std::vector<int> &out_list) {
	if (discovered[v] == false) {
		remains.push(v);
		discovered[v] = true;
	}

	while (remains.empty() == false) {
		int target_vertex = v = remains.front();
		out_list.push_back(target_vertex);
		remains.pop();

		std::vector<int> adjacents;
		for (int i = 0; i < MAX_VERTEX_CNT; ++i) {
			if (_board[v][i] == LINKED && discovered[i] == false) {
				remains.push(i);
				discovered[i] = true;
			}
		}
	}
}

void dfs(int v) {
	// 탐색된 정점에 대해 계속해서 탐색을 진행합니다.
	std::vector<bool> visited(MAX_VERTEX_CNT, false);
	std::vector<int> answer;

	// 
	dfs(v, visited, answer);
	for (int i = 0, len = answer.size(); i < len; ++i) {
		std::cout << answer[i] << ' ';
	}

	// 
	std::cout << newline;
}
void bfs(int v) {
	// 탐색된 정점에 연결된 모든 정점을 큐에 넣고 탐색합니다.
	std::vector<bool> discovered(MAX_VERTEX_CNT, false);
	std::vector<int> answer;
	std::queue<int> remains;

	// 
	bfs(v, discovered, remains, answer);
	for (int i = 0, len = answer.size(); i < len; ++i) {
		std::cout << answer[i] << ' ';
	}

	//
	std::cout << newline;
}

// 1260번: DFS와 BFS
int main(void) {
	std::cin.sync_with_stdio(false);

	// 
	int n, m, v;
	std::cin >> n >> m >> v;

	// 
	while (m--) {
		int v1, v2;
		std::cin >> v1 >> v2;
		link(v1, v2);
	}

	// 
	dfs(v);
	bfs(v);

	return 0;
}

ntopia 6년 전 4

정점 번호는 1번부터 N번까지이다.

ntopia 6년 전 1

for (int i = 0; i < MAX_VERTEX_CNT; ++i) {

hdnua 6년 전 0

@ntopia

처음에는 어차피 전체를 뒤지니까 상관 없는 조건이라고 생각했는데, 제 생각이 틀렸네요.

진심으로 감사드립니다. 앞으로 이런 조건에 더 신경 써서 코딩할 수 있겠어요.

brad903 5년 전 1

간선이 이어지지 않은 정점이 있는 케이스에서 반례를 찾았네요. 감사합니다!!

adfsfsf 5년 전 6

이런 케이스를 적으셨는데요, 아래가 맞는 것 같습니다.

qkrdbwls9601 5년 전 2

감사합니다 헤메다 주어진 반례보고 해결했습니다 !!

qbwvwdp 3년 전 2

반례 하나 더 올립니다.
참고하세요.
10 10 4 5 4 6 4 6 8 8 9 1 10 2 10 10 3 8 2 1 7 4 10 4 5 6 8 2 10 1 7 3 9 4 5 6 10 8 1 2 3 9 7

wlgh5014 2년 전 1

미천한 중생을 구제해주셔서 감사합니다 ㅜㅜ 드디어 해결!! 여기 반례들 통과하려고 조건 수정하다보니 맞았습니다!

mgcamper77 9달 전 1

감사합니다. 덕분에 해결했습니다. 정말 여기 아니었음 한참 고생할 뻔 했네요.

pajarito 3달 전 1

감사드립니다 : )

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

문제

문제

출처

ICPC

DFS와 BFS, 20%에서 구현이 틀렸습니다.

hdnua 6년 전 11

ntopia 6년 전 4

ntopia 6년 전 1

hdnua 6년 전 0

brad903 5년 전 1

adfsfsf 5년 전 6

qkrdbwls9601 5년 전 2

qbwvwdp 3년 전 2

wlgh5014 2년 전 1

mgcamper77 9달 전 1

pajarito 3달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말