글 읽기 - 살려주세요

zhoang3 7년 전 0

가르쳐주세요

도와주세요

알려주세요

틀렸습니다 떠요 ....

#include <iostream>
#include <stack>
#include <queue>

using namespace std;
int N, M, V;
int arr[1001][1001] = { 0, };
bool vstDF[1001] = { 0, };
bool vstBF[1001] = { 0, };

void Input() {
	
	scanf_s("%d %d %d", &N, &M, &V);
	vstBF[V] = true;
	vstDF[V] = true;

	while (M--) {
		int st, dt;
		scanf(" %d %d", &st, &dt);
		arr[st][dt] = 1;
		arr[dt][st] = 1;
	}
}

void DFS(int d) {
	for (int i = 1; i < 1001; i++) {
		if (arr[d][i] == 1 && !vstDF[i]) {
			printf(" %d", i);
			vstDF[i] = true;
			DFS(i);
			return;
		}
	}
}

void BFS() {
	queue<int> q;

	for (int i = V; i < 1001; i++) {
		if (arr[V][i] == 1) {
			q.push(i);
			vstBF[i] = true;
			printf(" %d", i);
		}
	}

	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		for (int i = 1; i < 1001; i++) {
			if (arr[tmp][i] == 1 && !vstBF[i]) {
				vstBF[i] = true;
				printf(" %d", i);
				q.push(i);
			}
		}
	}

}

int main() {
	Input();
	
	printf("%d", V);
	DFS(V);
	printf("\n");
	printf("%d", V);
	BFS();
	printf("\n");

}

syis00 7년 전 0

BFS 구문에서

방문할수 있는곳이 여러곳일때 정점번호가 낮은순부터 방문하셔야됩니다.

즉 queue에 (5 4 3)이 한번에 들어왔다면

(3 4 5) 순으로 방문하셔야 된다는 거죠

우선순위 큐를 추가로 쓰시는 걸 추천합니다.

ehddml3 7년 전 0

DFS 에 return 있는 것두 빼야할 것 같아요

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

문제

문제

출처

ICPC

살려주세요

zhoang3 7년 전 0

syis00 7년 전 0

ehddml3 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말