글 읽기 - 9470 문제 질문 드립니다.

moonsoo5522 6년 전 0

우선 위상정렬이 아닌 dfs+dp로 풀었습니다.

입력 데이터를 그대로 그래프로 구성하지 않고, 역방향 그래프를 만들었고,

바다로 나가는 강이 하나이기 때문에, 그 강에서부터 dfs를 돌리면서, 리프노드가 나올 경우 1을 리턴하고, 이외의 경우는 재귀함수의 리턴값의 최대값이 2개 이상이면 +1, 그렇지 않으면 최대 리턴값을 그대로 사용했습니다.(우선순위 큐는 리턴값의 최대값 2개를 검출하기 위함)

위상 정렬로 푸는게 정석이 문제라 사이클은 없을거라고 판단했고, 혹시나 dp가 문제일까 싶어서 dp 알고리즘도 제외하고 돌려봤는데 항상 50%에서 오답이 나네요.

어디가 문제일까요?

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;

int test;
int K, M, P;
vector< vector<int> > adj;
int dp[1001];
int visit[1001];

int solve(int node)
{
	if (!adj[node].size()) return 1;

	if (dp[node]) return dp[node];

	priority_queue<int> pq;
	for (int i = 0; i < adj[node].size(); i++)
	{
		int temp = solve(adj[node][i]);
		pq.push(temp);
	}

	int first_element = pq.top();
	pq.pop();

	if(!pq.empty())
	{
		int next_element = pq.top();
		pq.pop();
		if (first_element == next_element) return dp[node] = first_element + 1;
	}

	return dp[node] = first_element;
}
int main()
{
	scanf("%d", &test);
	while (test--)
	{
		scanf("%d %d %d", &K, &M, &P);
		adj = vector< vector<int> >(M + 1);

		int a, b;
		for (int i = 0; i < P; i++)
		{
			scanf("%d %d", &a, &b);
			adj[b].push_back(a);
			visit[a] = 1;
		}

		int N = M;
		for (int i = 1; i <= M; i++)
			if (!visit[i]) N = i;

		printf("%d %d", K, solve(N));
		memset(dp, 0, sizeof(dp));
	}
}

sgchoi5 6년 전 1

원 대회에서 공개된 TC 로 코드 문제점 한 번 찾아보실 수 있습니다..

http://gooddaytocode.blogspot.... 시도해보시길..

저는 제출한 코드가 틀렸다고 나올 때 어느 부분에서 틀렸을지 가늠해 보고 직접 반례를 찾아 보는 것이 실력 향상에 큰 도움을 준다고 생각합니다.
실력 향상을 위해서라면 대회에서 제공하는 데이터를 참고하는 것은 '문제점 한 번 찾아 보는' 데 사용하는 것이 아니라 문제를 푸는 데 있어 최후의 수단으로 생각되어야 마땅합니다.
"나는 도구를 제공해 줬을 뿐이고 사용하는 건 자기 몫이다"라고 터무니없는 변명으로 책임을 회피하실 분은 아니시리라 믿습니다.

덧붙여 대회 데이터가 질문자에게 도움이 많이 되냐 하면 그것도 아닐 가능성이 큽니다.
사소한 실수로 틀린 코드라면, 한두 글자를 고치기 위해서 몇십 개의 데이터를 다운로드받아 돌려 보는 것은 너무 큰 비용입니다. 자동화 스크립트를 짤 게 아니라면 손으로는 사실상 돌릴 수도 없습니다.
또한 사람이 직접 계산해 볼 수 있는 데이터의 크기는 한계가 있습니다. 예를 들어 최적해를 구하는 문제라면 반례를 찾더라도 그게 어떤 과정에 의해 최적해가 나왔는지를 직접 찾아야 하고, 반례가 손으로 계산할 수 있을 만큼 작지 않다면 무용지물입니다.

그리고 그 답변은 질문 게시판에 올라오는 대부분의 질문들보다 무성의합니다.
"데이터를 돌려 보세요" 하고 블로그 링크를 걸고, 질문자가 귀찮음을 무릅쓰고 돌려 본 다음 "다 잘 나와요" 하면 "데이터를 추가했나 보네요" 하고 마무리짓는 패턴을 몇 차례나 봐 왔습니다. 혹시 봇이라도 돌리시는 건가요?
URL 하나를 달랑 던져 놓는 답변은 심지어 질문을 읽을 필요조차 없으니 질문 작성자의 의도를 완전히 무시합니다. 게다가 답변할 의사가 있던 사람도 어쨌거나 답변이 달려 있으니 지나쳐 버릴 수 있습니다.

블로그에 관련 정보들을 정리하느라 많은 노력을 하셨을 거라는 건 이해합니다. 하지만 어차피 대회 사이트나 그 블로그 글은 대회 데이터가 필요할 정도로 절박한 사람이 구글에서 검색해 보면 다 나올 테고, 그걸 굳이 답변으로 달아 주실 필요는 없어 보입니다.

unused 6년 전 1

printf("%d %d", K, solve(N));

이걸

printf("%d %d\n", K, solve(N));

이렇게 고쳐보세요.

moonsoo5522 6년 전 0

@unused

아이고 감사합니다 ㅡㅡ;;

최근에 알고리즘을 소홀히 하다보니 이런데서 실수를 하네요 ㅠㅠ

sgchoi5 6년 전 0

@doju 말씀하신 내용을 보니.. 반성이 많이 되네요.. 앞으로는 공부에 더 신경을 쓰도록 하겠습니다.. ^^;;;

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

문제

문제

출처

ICPC

9470 문제 질문 드립니다.

moonsoo5522 6년 전 0

sgchoi5 6년 전 1

doju 6년 전 10

unused 6년 전 1

moonsoo5522 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말