글 읽기 - 반례가 무엇이 있을까요?

kth990303 3년 전 0

안녕하세요

먼저 제 접근법은 아래와 같습니다.

f는 함수이고, 함수는 단방향으로 하나의 노드로만 갈 수 있으므로

사이클에 속한 노드일 경우, 모든 노드들이 갈 수 있는 정점의 개수가 같을 것이라 판단하였고 이 때 fact('사이클의 크기 - 1')만큼 곱해주었고,

사이클과 바로 연결돼있는 노드는 사이클의 '갈 수 있는 정점의 개수' + 1일테고, 이 때 '사이클의 크기' 만큼 답에 곱해주었으며,

트리에 속한 노드와 연결돼있는 노드는 신경쓰지 않았습니다.

코드에 주석을 첨부하였고, 코드 아래에는 제가 임의로 만들어본 테스트케이스를 넣어보았습니다.

반례나 틀린 부분을 알 수 있을까요?

감사합니다

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const int MAX = 501;
const int MOD = 1e9 + 7;
ll N, ans = 1;
vector<int> v[MAX];
bool visit[MAX], cycle[MAX];
bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second > p2.second;
}
ll func(ll n) {
	if (!n)
		return 1;
	return n * func(n - 1);
}
void dfs(int cur, int size) {
	visit[cur] = true;
	for (auto i : v[cur]) {
        // 자기 자신은 탐색 x
		if (cur == i)
			continue;
        // 또 다른 노드가 이미 방문했던 사이클과 연결돼있을 때
		if (v[i].size() == size - 1 && cycle[i]) {
			ans *= (ll)v[i].size();
			ans %= MOD;
			return;
		}
		if (!visit[i]) {
            // 사이클인 경우
			if (size == v[i].size()) {
				visit[i] = true;
				cycle[i] = true;
				for (auto j : v[i]) {
                    // 사이클일 경우 갈 수 있는 정점의 개수가 서로 같음
					if (v[j].size() == v[i].size()) {
						cycle[j] = true;
						visit[j] = true;
					}
				}
                // 원순열 공식
				ans *= func((ll)size - 1);
				ans %= MOD;
				return;
			}
            // 정점이 사이클과 연결돼있지 않을 때
			else if (size == v[i].size() + 1) {
				visit[i] = true;
				dfs(i, v[i].size());
			}
            // 사이클이 아닌 정점이 사이클과 연결돼있을 때
            // if인 이유는 위에서 정점과 연결돼있는 부분이 사이클인지, 트리인지 판단한 후 처리해야되므로
			if (cycle[i]) {
				ans *= (ll)v[i].size();
				ans %= MOD;
				return;
			}
		}
	}
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	vector<pair<int, int>> k;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int n;
			cin >> n;
			if (n) {
				v[i].push_back(j);
			}
		}
		k.push_back({ i, v[i].size() });
	}
    // 갈 수 있는 정점 수가 많은 노드부터 탐색
	sort(all(k), cmp);
	for (int i = 0; i < N; i++) {
        // 컴포넌트 수가 여러 개일 수 있으므로
		if (!visit[i]) {
			dfs(k[i].first, k[i].second);
		}
	}
	cout << ans << "\n";
}


8
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 0 1 0
1 1 1 1 0 1 1 0
1 1 1 1 0 0 1 0
1 1 1 1 1 0 1 1
ans: 24

9
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
ans: 2


20
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
ans: 681893483


7
1 1 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 1 0 0 0
0 0 0 0 1 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
ans: 6

p_ce1052 3년 전 0

반례입니다

1 1 1

0 1 0

0 0 1

답 : 0

출력 : 1

kth990303 3년 전 1

@p_ce1052

감사합니다.

그런데 문제에서 가능한 함수가 존재하지 않는 경우는 입력으로 주어지지 않는다 돼있는데, 이 때 저는 답이 0인 경우는 입력으로 주어지지 않는다고 이해했는데 제가 잘못 이해한걸까요?

p_ce1052 3년 전 0

아 그러네요 죄송합니다

p_ce1052 3년 전 0

코드를 잠깐 봤는데 func 함수에서 mod연산을 안하는게 문제인 것 같네요 실제로

크기가 40인 사이클을 넣으니까 답이 다르게 나옵니다. AC맞으시길 바랍니다

kth990303 3년 전 0

@p_ce1052

func함수를 아래와 같이 수정했음에도 WA가 뜨네요 ㅠㅠ

혹시 괜찮으시다면 크기가 40인 사이클 반례를 알 수 있을까요?

ll func(ll n) {
	if (!n)
		return 1;
	return (n * (func(n - 1) % MOD)) % MOD;
}

p_ce1052 3년 전 1

n = 40에 모든 요소가 1인 40*40 행렬을 입력으로 넣었습니다.

제 코드는 444985875을 출력하는데

위에 올리신 코드는 526493625을 출력합니다.

kth990303 3년 전 1

@p_ce1052

아 func함수를 수정하니 위 반례는 444985875가 출력되는데 WA가 뜨는 거 보면

제 코드에서 고칠 곳이 한두 군데가 아닌가봅니다...

AC는 아니지만 반례 및 틀린부분을 제시해주셔서 정말 감사합니다.

p_ce1052 3년 전 1

1 1 1 1 1 1 0 0

0 1 1 1 1 1 0 0

0 0 1 1 1 1 0 0

0 0 0 1 1 1 0 0

0 0 0 1 1 1 1 0

0 0 0 1 1 1 0 1

이 입력에 대해서도 답이 다르네요 답은 54인데 6을 출력합니다.

도움이 되셨다니 다행이네요

kth990303 3년 전 1

@p_ce1052

정말 감사합니다. 덕분에 AC 맞았습니다

이문제 때문에 엄청 고생했는데 와.... 정말 감사드립니다

특히 마지막에 주신 반례가 정말 큰 도움이 됐습니다.

복받으세요 ㅜㅜㅜ 정말 감사합니다.

    for (int i = 0; i < N; i++) {
        // vector<pair<int, int>> k에 index, 그 인덱스의 갈수있는 정점의 개수
        
		if (!visit[i]) {
			dfs(k[i].first, k[i].second);
		}
	}


    // 즉 인덱스는 i가 아니고 k[i].first
    // 따라서 아래와 같이 수정 후 AC 맞았습니다

    for (int i = 0; i < N; i++) {
		if (!visit[k[i].first]) {
			dfs(k[i].first, k[i].second);
		}
	}

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

문제

문제

출처

ICPC

반례가 무엇이 있을까요?

kth990303 3년 전 0

p_ce1052 3년 전 0

kth990303 3년 전 1

p_ce1052 3년 전 0

p_ce1052 3년 전 0

kth990303 3년 전 0

p_ce1052 3년 전 1

kth990303 3년 전 1

p_ce1052 3년 전 1

kth990303 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말