글 읽기 - 상어의 저녁식사 문제인데 어디서 틀린건지 잘 모르겠습니다.

victory277 7년 전 0

상어의 각 정보를 받아서

잡아먹을 수 있는지에 대한 정보를 인접그래프로 만들어서

이분매칭을 2번 돌려서 구한 최대매칭값을 N에서 뺐습니다.

어떤 점에서 틀렸는지 가르침 주시면 감사하겠습니다.

#include <iostream>
using namespace std;

int shark[1000][3];
int d[1000][1000];
int N;
bool check[1000];
int Match[1000];

bool dfs(int a) {
	if (check[a]) return false;

	check[a] = true;

	for (int b = 0; b < N; b++) {
		if (d[a][b] == 1) {
			if (Match[b] == -1 || dfs(Match[b])) {
				Match[b] = a;
				return true;
			}
		}
	}

	return false;
}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> shark[i][0] >> shark[i][1] >> shark[i][2];
	}

	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (shark[i][0] >= shark[j][0] && shark[i][1] >= shark[j][1] && shark[i][2] >= shark[j][2]) {
				d[i][j] = 1;
			}
			else if (shark[i][0] < shark[j][0] && shark[i][1] < shark[j][1] && shark[i][2] < shark[j][2]) {
				d[j][i] = 1;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		Match[i] = -1;
	}

	int total = 0;

	for (int k = 0; k < 2; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				check[j] = false;
			}

			if(dfs(i)) total++;
		}
	}

	/*
	int live = 0;

	for (int i = 0; i < N; i++) {
		cout << Match[i] << " ";
		//if (Match[i] == -1) live++;
	}
	cout << endl;
	

	cout << live;
	*/

	cout << N - total;

	getchar();
	getchar();

	return 0;
}

simm4256 7년 전 0

얼핏 봐선

36번째줄 if문과 else if문부분에서

shark[i][n] == shark[j][n] (n=0,1,2)

일 때

d[i][j]과 d[j][i] 둘 다 1이어야 하는데

이 소스에선 d[i][j]는 1로 지정하지만 d[j][i]는 1로 지정하지 않는 것 같네요.

simm4256 7년 전 0

근데 사실 두 상어의 능력치가 같으면

A가 B를 먹나 B가 A를 먹나 같은 결과라 별 상관 없는 부분이긴 한데..

simm4256 7년 전 1

아, 39번째 else if문 조건에 의하면

A상어의 능력치가 10 15 20이고

B상어의 능력치가 10 15 25이면

d[A][B] = 0, d[B][A] = 0인 문제점이 발생하네요.

d[B][A] 설정하실 때 B상어의 능력치 '모두' A보다 커야 1이라고 조건을 걸으셨습니다.

victory277 7년 전 0

감사합니다!!!

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

문제

문제

출처

ICPC

상어의 저녁식사 문제인데 어디서 틀린건지 잘 모르겠습니다.

victory277 7년 전 0

simm4256 7년 전 0

simm4256 7년 전 0

simm4256 7년 전 1

victory277 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말