글 읽기 - 뭐가 잘못된지 모르겠습니다. 반례좀 찾아주세요

kksshh0612 2년 전 0

스택과 큐로 그래프 탐색을 구현했습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define max_vertex 1001				//정점 최대 갯수 인덱스 0을 사용하지 않기 때문에 1을 더해줌

int graph[max_vertex][max_vertex] = { 0, };		//인접행렬
int DFS_visited[max_vertex] = { 0, };	//DFS방문여부 확인할 행렬
int BFS_visited[max_vertex] = { 0, };	//BFS방문여부 확인할 행렬

//스택과 큐 관련--------------------------------
typedef struct node {
	int vertex;			//스택에 넣을 정점
	struct node* next;
}node;

node* top = NULL;		//스택 top포인터
node* front = NULL;		//큐에서 값 꺼낼 위치
node* rear = NULL;		//큐에서 갑 삽입할 위치
int queue_size = 0;		//큐에 들어있는 원소들 수
int is_stack_empty();
void push(int v);
int pop();
int is_queue_empty();
void enqueue(int v);
int dequeue();
//----------------------------------------------

void DFS(int start_vertex, int vertex_size) {			//v는 탐색 시작할 정점, vertex_size는 정점 개수
	int search_vtx = 0, cnt = 0, check = 0;			//탐색할 정점, 카운트 변수
	DFS_visited[start_vertex] = 1;
	cnt++;
	printf("%d", start_vertex);		//탐색 시작 정점 출력
	push(start_vertex);
	search_vtx = start_vertex;

	while (cnt < vertex_size) {					//찾은 정점 수가 총 정점 수와 같을때까지 반복
		check = 0;		//초기화
		for (int i = 1; i <= vertex_size; i++) {
			if (graph[search_vtx][i] == 1 && DFS_visited[i] == 0) {			//인접하고 방문하지 않은 정점 찾으면
				search_vtx = i;					//다음 이동할 정점
				DFS_visited[search_vtx] = 1;
				push(search_vtx);
				cnt++;							//탐색한 정점 수
				check = 1;						//인접한 정점 찾았으면 check 1로
				printf(" %d", search_vtx);
				break;
			}
		}
		if (check == 0) {						//인접한 정점 없으면
			if (is_stack_empty() != 1) {
				search_vtx = pop();				//뒤로 돌아가면서 찾기
			}
			else return;						//stack이 비었으면 함수 탈출
		}
	}
}

void BFS(int start_vertex, int vertex_size) {
	int search_vtx = 0, cnt = 0;
	BFS_visited[start_vertex] = 1;
	cnt++;
	printf("\n");			
	printf("%d", start_vertex);
	enqueue(start_vertex);
	search_vtx = start_vertex;				//인접 정점 찾을 정점

	while (cnt < vertex_size) {				//탐색한 정점 수가 총 정점 수와 같을때까지 반복
		for (int i = 1; i <= vertex_size; i++) {
			if (graph[search_vtx][i] == 1 && BFS_visited[i] == 0) {				//인접하고 방문하지 않은 정점 찾으면
				BFS_visited[i] = 1;
				enqueue(i);
				printf(" %d", i);
				cnt++;
			}
		}
		if (is_queue_empty() != 1) {
			search_vtx = dequeue();			//큐에서 하나 빼서 그 정점의 인접정점 탐색
		}
	}
}

int main() {
	int vertex = 0, edge = 0, start_vertex = 0;
	int vtx1 = 0, vtx2 = 0;
	scanf("%d %d %d", &vertex, &edge, &start_vertex);		//정점수, 엣지수, 탐색 시작 정점
	for (int i = 0; i < edge; i++) {
		scanf("%d %d", &vtx1, &vtx2);						//연결할 두 정점 입력
		graph[vtx1][vtx2] = 1;								//인접행렬 해당 위치 1로 초기화. 무방향그래프이기 때문에 행<->열 바꿔서도 초기화해줌
		graph[vtx2][vtx1] = 1;
	}
	DFS(start_vertex, vertex);
	BFS(start_vertex, vertex);

	return 0;
}

int is_stack_empty() {
	if (top == NULL) {			//스택이 비었으면 1 리턴
		return 1;
	}
	return 0;					//비어있지 않으면 0 리턴
}

void push(int v) {
	node* newnode = (node*)malloc(sizeof(node));
	newnode->vertex = v;		//방문한 정점 스택에 삽입
	newnode->next = top;
	top = newnode;
}

int pop() {
	if (is_stack_empty() != 1) {
		node* remove_node = top;
		int val = remove_node->vertex;			//스택에서 꺼낼 정점
		top = remove_node->next;
		free(remove_node);
		return val;
	}
	else {					//스택이 비었으면 -1 리턴
		return -1;
	}
}

int is_queue_empty() {
	if (queue_size == 0) {				//큐가 비었으면 1 리턴
		return 1;			
	}
	return 0;							//큐가 비어있지 않으면 0 리턴
}

void enqueue(int v) {					//큐에 삽입
	node* newnode = (node*)malloc(sizeof(node));
	newnode->vertex = v;
	newnode->next = NULL;
	if (is_queue_empty() == 1) {		//큐가 비어있으면
		front = newnode;
	}
	else {
		rear->next = newnode;			//큐가 비어있지 않으면 rear의 다음 노드에 newnode 연결
	}
	rear = newnode;						//rear가 새로 추가된 노드를 가리킴
	queue_size++;						//
}

int dequeue() {
	if (is_queue_empty() == 1) {
		return -1;						//큐가 비었으면 -1 리턴
	}
	node* remove_node = front;			//삭제할 노드 포인터가 front가 가리티는 노드를 가리킴
	int val = remove_node->vertex;		//삭제할 노드의 value
	front = remove_node->next;			//front를 다음노드로 이동
	free(remove_node);					//노드 해제
	queue_size--;						//큐 사이즈 -1

	return val;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

뭐가 잘못된지 모르겠습니다. 반례좀 찾아주세요

kksshh0612 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
