글 읽기 - 알고리즘 지적해주시면 감사합니다!

sochun1518 3년 전 0

[ 정의 ]

주어진 그래프에서 x가 y번 블록을 넘어트리면 push[x] 배열에 y를 추가하고, pushed[y] 배열에는 x를 추가했습니다.

push[i] := i번 블록이 넘어지면서 넘어트리는 블록들

pushed[i] := i번 블록을 넘어트리는 블록들

[ 아이디어 ]

자기 자신을 넘어트리는 블록이 가장 적으면서 자기 자신이 넘어지면서 넘어트리는 블록이 가장 많은 블록이 무조건적으로 유리하다고 판단했습니다.

그래서 priority_queue를 이용해

1) 나를 넘어트리는 블록이 가장 적은 블록

2) 내가 넘어트리는 블록이 가장 많은 블록

을 1, 2순위 기준으로 부여해서 해당 블록을 BFS탐색을 진행했습니다.

40% 에서 틀렸습니다를 받으며 게시물에 있는 예제 케이스는 다 통과했습니다.

조언 주시면 감사합니다!

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int T, N, M, x, y, ans;
vector<int> push[100001];
vector<int> pushed[100001];
bool visited[100001];

void set(void) {
	ans = 0;
	for (int i = 1; i <= N; i++) {
		push[i].clear();
		pushed[i].clear();
		visited[i] = false;
	}
}

void BFS(int s) {
	queue<int> q;
	q.push(s);
	visited[s] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int next : push[cur]) {
			if (!visited[next]) {
				visited[next] = true;
				q.push(next);
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> T;
	while (T--) {
		cin >> N >> M;

		set();

		for (int i = 0; i < M; i++) {
			cin >> x >> y;
			push[x].push_back(y); // x를 넘어짐 -> y가 넘어짐
			pushed[y].push_back(x); // y를 x가 넘어트림
		}

		// 자기를 넘어트리는 블록이 제일 없고, 다른 블록을 제일 많이 넘어트리는 블록
		priority_queue<pair<pair<int, int>, int>> pq;
		for (int i = 1; i <= N; i++) {
			pq.push({ { -(int)pushed[i].size(), (int)push[i].size() }, i });
		}

		while (!pq.empty()) {
			int ind = pq.top().second;
			pq.pop();

			if (visited[ind]) continue;

			BFS(ind);
			ans++;
		}
		cout << ans << '\n';
	}

	return 0;
}

nuclear852 3년 전 1

반례 첨부합니다.

양방향 단선일경우 어떻게 처리해야할까요?

고민을 한 번 해보시면 좋을 것 같습니다.

1
7
1
3
2
4
3
2
4
// 출력 : 2
// 답 : 1

sochun1518 3년 전 0

답글 감사드립니다!!

좋은 반례가 있었군요....!!

다시 고민해보도록 하겠습니다 :))

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

문제

문제

출처

ICPC

알고리즘 지적해주시면 감사합니다!

sochun1518 3년 전 0

nuclear852 3년 전 1

sochun1518 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말