글 읽기 - 1766번 고수님들 부탁드립니다.. ㅜ

khx5558 5년 전 0

indegree 가 0 인 vertex를 priority_queue 에 넣고 낮은 순으로 뺴 쓰는 방법으로 풀어서 맞았어서,

반대 방향 으로 DFS 로 푸는 방법으로 풀어보고 싶어 코드를 짜보았는데 여러 케이스(질문 게시판 반례 모두 등)들을 입력 했을 떄는 맞게 나오느데, 체점하니 계속 틀렸다고 나오네요 ㅜㅜ

혹시 반례나, 틀린이유 혹은 DFS로 풀면 답이 될수 없는 이유 를 알려주실 고수님 계신가요 ㅜㅜㅜ
굽신 굽신...

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

vector<priority_queue<int>> adjList;
vector<bool> visited;
vector<int> list;
int N, M;
void DFS(int v);

int main() {
	int u, v;

	cin >> N >> M;
	adjList = vector<priority_queue<int>>(N);
	visited = vector<bool>(N, false);

	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		adjList[u - 1].push(v - 1);
	}

	for (int i = N - 1; i >= 0; i--)
		if (visited[i] == false) {
			visited[i] = true;
			DFS(i);
		}

	while (!list.empty()) {
		cout << list.back() << " ";
		list.pop_back();
	}
}

void DFS(int v) {
	cout << v << '\n';
	priority_queue<int> temp = adjList[v];
	while (!temp.empty()) {
		int next = temp.top();
		temp.pop();
		if (visited[next] == false) {
			visited[next] = true;
			DFS(next);
		}
	}
	list.push_back(v + 1);
}

djm03178 5년 전 3

아래와 같은 입력에서 틀립니다.

틀리는 원인은, 4에 연결된 두 정점 1, 2만 보고 이 중 더 큰 쪽을 먼저 들어가서 마지막에 빠지게 하는 것이 유리할 것이라고 생각했지만, 실제로는 1이 먼저 처리된 후 3과 2도 비교를 해야만 정말로 그게 이득인지 알 수 있었기 때문입니다.

4
1
3
2
2
output: 4 1 3 2
correct answer: 4 1 2 3

khx5558 5년 전 0

DFS로 안풀리는 경우였군요 정말 갑사합니다.. ㅠㅠ

새해복 많이 받으세요~

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

문제

문제

출처

ICPC

1766번 고수님들 부탁드립니다.. ㅜ

khx5558 5년 전 0

djm03178 5년 전 3

khx5558 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말