글 읽기 - 값은 제대로 나오는데 바로틀렸다고 나옵니다.

kaiose 6년 전 0

왜그럴까요
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string.h>
//Depth First Search
//Breadth First Search
//단 방문할수 있는 정점이 여러 개인경우 정점번호가 작은것을 먼저방문하고
// 방문할수 있는 점이 없는 경우 종료한다.

struct node {
	node* next;
	int data;
};

struct stack {
	node* Head;
	int length;
	stack() {
		Head = NULL;
		length = 0;
	}
	void push_back(int data) {
		node* temp = new node;
		temp->data = data;
		if (Head == NULL) {
			Head = temp;
		}
		else {
			temp->next = Head;
			Head = temp;
		}
		length++;
	}

	bool search(int data) {
		if (Head == NULL) {
			return false;
		}
		else {
			node* temp = Head;
			for (int i = 0; i < length; i++) {
				if (temp->data == data) return true;
				if(temp->next != NULL)
					temp = temp->next;
			}
			return false;
		}
	}

	int back() {

		if (Head == NULL) return -1;
		int result = Head->data;
		node* temp = Head;
		Head = Head->next;
		delete temp;
		return result;
	}
};

struct queue {
	// 넣는 방식은 뒤에 이어붙이는 식으로 하되 빼내는 방식은 Stack 과 같다
	node* Head;
	int length;
	queue() {
		Head = NULL;
		length = 0;
	}

	int back() {
		if (Head == NULL) return -1;
		else {
			return Head->data;
		}
	}

	void push_back(int data) {
		node* temp = new node;
		temp->data = data;
		if (Head == NULL) {
			Head = temp;
		}
		else {
			if (length == 1) {
				Head->next = temp;
			}
			else {
				node* temp2 = Head;
				for (int i = 0; i < length - 1; i++) {
					temp2 = temp2->next;
				}
				temp2->next = temp;
			}
		}
		length++;
	}

	int pop_up() {
		if (Head == NULL) return -1;
		else {
			int data = 0;
			if (length == 1) {
				data = Head->data;
				Head = NULL;
			}
			else {
				node* temp = Head;
				data = Head->data;
				Head = Head->next;
				delete temp;
			}
			length--;
			return data;
		}
	}

};

void DFS(int** map, int start, int size, stack* storage) {
	/*
	탈출루프는 방문한노드의 갯수가 size가 된다면 탈출이다.
	방문할수 있는 노드가 있다면 방문
	없다면 부모노드로 이동
	*/
	if (storage->length == size) {
		printf("%d", start);
		return;
	}
	if(!storage->search(start))
		storage->push_back(start);
	int i = 0;
	for (i = 0; i < size; i++) {
		if (i == start - 1) continue;
		if (map[start - 1][i] == 1 && !storage->search(i + 1)) {
			printf("%d", start);
			return DFS(map, i + 1, size, storage);
		}
	}
	return DFS(map, storage->back(), size, storage);

}

void BFS(int** map, int start, int size, queue* storage, stack* visit) {
	if (storage->length == 0 || visit->length == 0) {
		storage->push_back(start);
	}
	else if (visit->length == size) {
		return ;
	}
//	첫번 째 start 를 넣는 것을 관리해줘야 함,
	visit->push_back(storage->back());

	for (int i = 0; i < size; i++) {
	
		if (i == start - 1) continue;
		
		if (map[start - 1][i] == 1 && !visit->search(i+1)) {
		
			storage->push_back(i + 1);			
		
		}
	}
	printf("%d", storage->back());

	return BFS(map, storage->pop_up(), size, storage, visit);
	/*
		큐에 넣고 
		큐 빼면서 뺀 데이터와 연결된 다른 데이터를 확인한다.
		확인한데이터중에 방문하지 않은 데이터가 있으면
		)큐에 넣는다.
	*/

}
int main() {
	int N = 0;
	int M = 0;
	int start = 0;
	scanf("%d%d%d", &N,&M,&start);
	int** map = new int*[N];
	for (int i = 0; i < N; i++) {
 	map[i] = new int[N];
	}
	int v1 = 0, v2 = 0;
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &v1, &v2);
		map[v1-1][v2-1] = 1;
		map[v2-1][v1-1] = 1;
	}
	stack visit;
	DFS(map, start,N,&visit );
	printf("\n");
	stack visit1;
	queue storage;
	BFS(map, start,N,&storage,&visit1);
	for (int i = 0; i < N; i++) {
		delete[] map[i];
	}
	delete[] map;
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

값은 제대로 나오는데 바로틀렸다고 나옵니다.

kaiose 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
