글 읽기 - 어떤 부분에서 논리적으로 오류가 있는지 모르겠습니다 ㅠㅠ 반례가 있을까요 ?

sujae03 6년 전 0

dfs를 이용하여 위상정렬 하여 문제를 풀었습니다.

1. 먼저 풀면 좋은 조건에 따라 그래프를 만들어줍니다.

A B라면, A->B 될 수 있도록 방향 그래프 생성

2. 가장 어려운 문제인 N부터 가장 쉬운 문제인 1까지 차례대로 for문을 돌면서

2-1) 만약, 지금 가리키는 index 문제 번호보다 나중에 풀어야 할 것이 없다면 stack에 넣어주고,

2-2) 그렇지 않고 지금 가리키는 index 문제 번호보다 나중에 풀어야 할 것이 있다면 dfs함수로 점프합니다.

3. dfs함수에서는 위상정렬 알고리즘을 이용합니다.

A-> B

A-> C

우선, A->B 가 아닌 A->C (큰 값부터) 돌 수 있도록 내림차순 정렬을 해주고,

dfs를 돌며 위상정렬을 합니다.

이렇게 해서 제가 직접 test case 만들어보면서 실행했는데

어떠한 반례도 못찾겠습니다 ㅠㅠ

도와주세요

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
#include <stack>
using namespace std;
int N, M;
stack <int> s;
vector <int> vec[32001];
int visit[32001];
int ind[32001];
void input()
{
	int u = 0, v = 0;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d%d", &u, &v);
		vec[u].push_back(v);
		ind[u]++;
	}
}
void dfs(int u)
{
	int size = vec[u].size();
	sort(vec[u].begin(), vec[u].end(), greater <int>());
	for (int i = 0; i < size; i++)
	{
		if (visit[vec[u][i]]) { continue; }
		visit[vec[u][i]] = 1;
		dfs(vec[u][i]);
		s.push(vec[u][i]);
	}
}
int main(void)
{
#ifdef _WIN32
	freopen("in.txt", "r", stdin);
#endif // _WIN32


	// 입력
	input();		


	//계산
	for (int i = N; i >= 1; i--)
	{
		if (visit[i]) { continue; }			//방문했던 노드는 패스
		visit[i] = 1;
		if (!ind[i]) { s.push(i); continue; }// i번째 노드보다 먼저 와야하는 것이 없다면, stack에 넣어준다.
		dfs(i);									// i번째 노드보다 먼저 와야하는 것이 있다면, 위상정렬
		s.push(i);
	}

	//출력
	while (!s.empty())
	{
		printf("%d ", s.top());
		s.pop();
	}
	printf("\n");
	return 0;
}

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

문제

문제

출처

ICPC

어떤 부분에서 논리적으로 오류가 있는지 모르겠습니다 ㅠㅠ 반례가 있을까요 ?

sujae03 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말