글 읽기 - 상어의 저녁식사 & 열혈강호2 차이점 질문입니다.

kkw564 7년 전 0

예전 열혈강호2 문제를 푼것과 동일하게 상어 저녁식사 코드에서 visit를 처리해주니 WA를 받았습니다.

가장 첫번째 코드는 상어 식사 WA 코드인데 왜 visit를 저렇게 처리해주면 안되나요?

저렇게 하면 나중에 이분 매칭에서 문제가 되나요??

그런데 열혈강호 2에서는 저렇게 visit를 처리하니 AC를 받았습니다.(2번째 코드는 댓글에 올려두겠습니다.)

그리고 열혈강호 2 문제를 VISIT를 초기화 하지 않고 visitCnt를 통해 처리를 해주니 시간이 3배가량 더 증가하였습니다.

계속해서 초기화 하는 것 보다 변수로 visit를 구분해주는게 더 시간이 오래 걸린다는 것이 이해가 되지 않네요..(3번째 코드는 그다음 댓글에 달아두겠습니다..)

고수님들. 도와주세요

// 상어 저녁 WA코드, 왜 visit를 저렇게 처리해서 2번 방문하는 개념으로 이용하면 안되나요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>

#define MAX_N 1002

using namespace std;

typedef struct _JAWS_
{
	int size;
	int speed;
	int intel;
}JAWS;
int n;
JAWS jaws[MAX_N];
bool adj[MAX_N][MAX_N];
int aMatch[MAX_N];
int bMatch[MAX_N];

int visit[MAX_N];

bool dfs(int a)
{
	if (visit[a] > 1)
		return false;

	visit[a]++;
	for (int b = 1; b <= n; b++)
	{
		if (adj[a][b])
		{
			if (bMatch[b] == -1 || dfs(bMatch[b]))
			{
				aMatch[a] = b;
				bMatch[b] = a;

 				return true;
			}
		}
	}
	return false;
}
int bipartiteMatch()
{
	int size = 0;

	memset(aMatch, -1, sizeof(aMatch));
	memset(bMatch, -1, sizeof(bMatch));
    
	for (int a = 1; a <= n; a++)
	{
		memset(visit, 0, sizeof(visit));
		size += dfs(a);
		size += dfs(a);
	}

	return size;
}

int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		int size, speed, intel;
		scanf("%d %d %d", &size, &speed, &intel);

		jaws[i].size = size;
		jaws[i].speed = speed;
		jaws[i].intel = intel;
	}


	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				continue;

			if (jaws[i].size == jaws[j].size && jaws[i].speed == jaws[j].speed && jaws[i].intel == jaws[j].intel && i > j)
				continue;

			if (jaws[i].size >= jaws[j].size && jaws[i].speed >= jaws[j].speed && jaws[i].intel >= jaws[j].intel)
				adj[i][j] = 1;
		}
	}


	int cnt = bipartiteMatch();

	printf("%d\n", n - cnt);

	return 0;
}

kkw564 7년 전 0

상어에서는 WA / 열혈 2에서는 AC를 받은 visit방식입니다.

// ​상어에서는 WA / 열혈 2에서는 AC를 받은 visit방식입니다.

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m, k;

// adj[i][j] = Ai와 Bj가 연결되어 있는가?
bool adj[1001][1001];

// 각 정점에 매칭된 상대 정점의 번호를 지정한다.
vector<int> aMatch, bMatch;

// dfs()의 방문 여부
vector<int> visited;

bool dfs(int here)
{
	if (visited[here] > 0)
		return false;

	visited[here] ++;

	for (int there = 0; there < m; there++)
	{
		// adj가 존재하면
		if (adj[here][there])
		{
			// bMatch에 아직 매치가 안되있거나,
			// 매칭 되어있다면 dfs를 통해 aMatch의 연결 된 것을 재 탐색 시킨다.
			if (bMatch[there] == -1 || dfs(bMatch[there]))
			{
				aMatch[here] = there;
				bMatch[there] = here;

				return true;
			}
		}
	}
	return false;
}
int main()
{
	int size = 0;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &k);

		for (int j = 0; j < k; j++)
		{
			int pos;
			scanf("%d", &pos);

			adj[i][pos - 1] = 1;
		}
	}

	aMatch = vector<int>(n, -1);
	bMatch = vector<int>(m, -1);

	for (int start = 0; start < n; start++)
	{
		visited = vector<int>(n, -1);

		// 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.
		if (dfs(start))
			size++; 

		if (dfs(start))
			size++;
	}

	cout << size;

	return 0;
}

kkw564 7년 전 0

열혈2 AC코드입니다.

visit를 위에서는 초기화를 계속했지만 아래에서는 visitCnt로 시간을 단축하려했지만 되려 시간이 늘어나네요 이유가 궁금합니다.

// ​열혈2 AC코드입니다. 

// visit를 위에서는 초기화를 계속했지만 아래에서는 visitCnt로 시간을 단축하려했지만 되려 시간이 늘어나네요 이유가 궁금합니다.
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int n, m, k;

// adj[i][j] = Ai와 Bj가 연결되어 있는가?
bool adj[1001][1001];

// 각 정점에 매칭된 상대 정점의 번호를 지정한다.
vector<int> aMatch, bMatch;

// dfs()의 방문 여부
int visited[1001];
int visitCnt = 1;

bool dfs(int here)
{
	if (visited[here] == visitCnt)
		return false;

	visited[here] = visitCnt;

	for (int there = 0; there < m; there++)
	{
		// adj가 존재하면
		if (adj[here][there])
		{
			// bMatch에 아직 매치가 안되있거나,
			// 매칭 되어있다면 dfs를 통해 aMatch의 연결 된 것을 재 탐색 시킨다.
			if (bMatch[there] == -1 || dfs(bMatch[there]))
			{
				aMatch[here] = there;
				bMatch[there] = here;

				return true;
			}
		}
	}
	return false;
}
int main()
{
	int size = 0;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &k);

		for (int j = 0; j < k; j++)
		{
			int pos;
			scanf("%d", &pos);

			adj[i][pos - 1] = 1;
		}
	}

	aMatch = vector<int>(n, -1);
	bMatch = vector<int>(m, -1);

	for (int start = 0; start < n; start++)
	{
		// 깊이 우선 탐색을 이용해 start에서 시작하는 증가 경로를 찾는다.
		visitCnt++;
		if (dfs(start))
			size++;
		visitCnt++;
		if (dfs(start))
			size++;
	}

	cout << size;

	return 0;
}

baekjoon 7년 전 0

자기 자신을 먹으면 안되기 때문입니다.

kkw564 7년 전 0

if (i == j)
continue;

를 통해 자기 자신을 먹는다는 개념은 배제한 상태인데 그게 가능한 일인가요??

baekjoon 7년 전 1

그렇네요 .... ㅈㅅ

kkw564 7년 전 0

ㅋㅋㅋ 해답을주세요 백준님. .ㅠ 수업도 또 열어주시면 좋겠어요 ㅠㅠ 처음가봤는데 너무 좋았어요

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

문제

문제

출처

ICPC

상어의 저녁식사 & 열혈강호2 차이점 질문입니다.

kkw564 7년 전 0

kkw564 7년 전 0

kkw564 7년 전 0

baekjoon 7년 전 0

kkw564 7년 전 0

baekjoon 7년 전 1

kkw564 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말