글 읽기 - 1260 DFS BFS 반례가 궁금합니다.

shkk0628 2년 전 0

백준 질문 게시판도 참고하고, 저 스스로 다양한 예제를 넣어봤는데 답이 안나와서 질문드립니다.

혹시 다른 반례가 있을까요?? 아래는 구현 방식에 대한 간략한 설명입니다.

DFS는 따로 스택을 구현하지 않고 재귀를 이용했습니다.

BFS는 간단한 원형 큐를 구현해서 만들었습니다.

인접행렬 정보를 이용했습니다.

정점 번호와 인접행렬의 인덱스 값을 똑같이 이용하기 위해서 N+1개 만큼을 할당했습니다.

DFS는 방문정보를 초기화하고 시작정점으로 재귀를 시작합니다.

이미 방문한 정점인 경우 별다른 작업 없이 재귀 탈출

매개변수로 받은 정점을 방문(출력, 방문체크)

그 정점과 연결된 정점으로 재귀 반복

BFS는 방문정보를 초기화하고 시작정점을 큐에 넣습니다.

큐가 비어있을 때까지 반복합니다.

큐에서 정점을 하나 꺼냅니다.

그 정점이 방문한 정점이라면 다음 반복으로 넘어갑니다.

방문하지 않았다면, 방문(출력, 방문체크)

그 정점과 연결된 정점을 큐에 넣습니다.

DFS BFS 둘 다 일단 재귀 혹은 큐에 넣어보고

방문했었다면 별다른 작업을 하지 않는 형태로 구현했습니다.

(재귀나 en큐 전에 방문 검사를 하는 방법이 아닙니다.)

#include <stdio.h>
#include <stdlib.h>

int	front = -1;
int	rear = -1;
int	queue[10000];

int	is_empty(void)
{
	return (front == rear);
}

int	enqueue(int V)
{
	rear = (rear + 1) % 10000;
	queue[rear] = V;
	return (queue[rear]);
}

int	dequeue(void)
{
	front = (front + 1) % 10000;
	return (queue[front]);
}

void	BFS(int **adj, int N, int V)
{
	int	visited[N + 1];
	int	curr_V;

	for (int i = 1; i <= N; i++)
		visited[i] = 0;
	enqueue(V);
	while (!is_empty())
	{
		curr_V = dequeue();
		if (visited[curr_V])
			continue ;
		printf("%d ", curr_V);
		visited[curr_V] = 1;
		for (int i = 1; i <= N; i++)
			if (adj[curr_V][i])
				enqueue(i);
	}
}

void	rDFS(int **adj, int *visited, int N, int V)
{
	if (visited[V])
		return ;
	printf("%d ", V);
	visited[V] = 1;
	for (int i = 1; i <= N; i++)
	{
		if (adj[V][i])
			rDFS(adj, visited, N, i);
	}
}

void	DFS(int **adj, int N, int V)
{
	int	visited[N + 1];

	for (int i = 1; i <= N; i++)
		visited[i] = 0;
	rDFS(adj, visited, N, V);
	printf("\n");
}

int	main()
{
	int	**adj_matrix;
	int	N, M, V;
	int	v1, v2;

	scanf("%d %d %d", &N, &M, &V);
	adj_matrix = (int **)malloc(sizeof(int *) * (N + 1));
	for (int i = 1; i <= N; i++)
		adj_matrix[i] = (int *)calloc(N + 1, sizeof(int));
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &v1, &v2);
		adj_matrix[v1][v2] = 1;
		adj_matrix[v2][v1] = 1;
	}
	DFS(adj_matrix, N, V);
	BFS(adj_matrix, N, V);
	for (int i = 1; i <= N; i++)
		free(adj_matrix[i]);
	free(adj_matrix);
	return (0);
}


/*
5 7 1
1 2
1 4
5 1
3 5
4 3
3 1
2 3
*/

/*
8 12 7
1 2
2 4
4 7
3 6
6 1
7 6
7 8
1 3
2 7
1 4
2 5
7 5
*/

/*
6 9 1
3 5
1 3
4 1
2 3
3 4
6 4
3 6
1 2
2 5
*/

/*
8 12 4
1 2
2 4
4 7
3 6
6 1
7 6
7 8
1 3
2 7
1 4
2 5
7 5
*/

flappybird 2년 전 1

원형 큐를 구현해 사용하신 이유를 알 수 있을까요?

그리고 C언어 문법만을 사용하시는 것으로 보이는데, C++의 스택, 큐 등의 자료형을 배워보시는것도 추천드립니다. 겁나 편해요

shkk0628 2년 전 0

맞습니다.. cpp 공부하는 중이지만, c로 진행하는 프로젝트를 병행하다 보니 딱 잡고 공부할 기회가 많지 않았네요

이번에 휴학하고 주 언어로 사용할 수 있도록 공부할 생각입니다.

원형 큐로 구현 한 이유는 cpp를 사용하지 않고 c만 사용하는 제가

최대한 다른 자료구조형이 필요할 때, 빠르고 간단하게 구현 할 수 있는 꼼수를 연구하다 나온 큐의 최종 버전입니다...

그리고 사실 c로 빡구현에 도전하다 보면 복습도 되고, 희열도 느끼고 그런 맛이 있습니다 (광기)

애매한 cpp실력으로 문제에 집중하지 못할 바에는, 문법 걱정 없이 생각나는 대로 작성할 수 있는 c를 사용 중 입니다 하하

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

문제

문제

출처

ICPC

1260 DFS BFS 반례가 궁금합니다.

shkk0628 2년 전 0

flappybird 2년 전 1

shkk0628 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말