글 읽기 - 1260 C++ 질문입니다.

naks 3년 전 0

주어진 예시 3개는 다 만족을 하는데 틀렸다고 나옵니다.

혹시 반례나 어떻게 고쳐야 할지 피드백 좀 주시면 감사하겠습니다!!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int N, M, S;
int map[1001][1001] = { 0 };

//dfs
bool d_visited[1001];
vector<int> d_answer;

//bfs
bool b_visited[1001];
vector<int> b_answer;

int dfs(int x, int y) {
	d_visited[y] = true;
	int count = 0;
	for (int i = 1; i <= N; i++)
	{
		if (y == i)
			continue;
		if (map[y][i] == 1 && !d_visited[i])
		{
			d_answer.push_back(i);
			dfs(y, i);
		}
	}
	return count;
}

int bfs(int x, int y) {
	b_visited[y] = true;
	int count = 0;
	for (int i = y + 1; i <= N; i++)
	{
		if (x == i)
			continue;
		if (map[x][i] == 1 && !b_visited[i])
		{
			b_answer.push_back(i);
			count = bfs(x, i);
			count = i;

		}
	}
	return count;
}

int main(void) {
	cin >> N >> M >> S;

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}



	//dfs 계산과정
	d_answer.push_back(S);
	d_visited[S] = true;
	for (int j = 1; j <= N; j++) {
		if (S == j)
			continue;
		int flag = 0;
		if (map[S][j] == 1 && !d_visited[j])
		{
			for (int k = 0; k < d_answer.size(); k++)
			{
				if (d_answer[k] == j)
					flag = 1;
			}
			if (flag == 0)
			{
				d_answer.push_back(j);
				dfs(S, j);
			}
		}
	}
	for (int k : d_answer)
	{
		cout << k << ' ';
	}
	cout << '\n';

	//bfs 계산과정
	b_answer.push_back(S);
	b_visited[S] = true;
	int temp = S;
	for (int i = 1; i <= N; i++)
	{
		int flag = 0;
		for (int j = b_answer.size()-1; j >= 0; j--)
		{
			flag = 0;
			if (map[b_answer[j]][i] == 1 && !b_visited[i])
			{
				for (int k = 0; k < b_answer.size(); k++)
				{
					if (b_answer[k] == i)
						flag = 1;
				}

				if (flag == 0)
				{
					b_answer.push_back(i);
					bfs(b_answer[j], i);
				}
			}
		}
		if (flag == 1)
			break;
	}
	for (int k : b_answer)
	{
		cout << k << ' ';
	}
	return 0;
}

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

문제

문제

출처

ICPC

1260 C++ 질문입니다.

naks 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말