백준 10552 - DOM(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10552

10552번: DOM

추상적인 그래프 표현이였기에 생각보단 어려웠던 문제입니다.

싫어하는 채널이 틀어져 있을 경우 나이가 가장 어린 사람이 자신이 가장 좋아하는 채널로 돌립니다.

따라서 X번 채널과 X번 채널을 싫어하는 사람 중 나이가 가장 어린 사람이 좋아하는 채널을 같이 저장해주면 됨을 알 수 있습니다.

 

이러한 과정으로 아무도 싫어하는 채널이 나올 때까지 반복해주면 됩니다.

그러지 못한다면 -1을 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int N, M, P;
int check[100001];
vector<int> dislike[100001];

int bfs(int start) {
	int cnt = 0;
	queue<int> q;
	check[start] = 1;
	q.push(start);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (!dislike[x].size()) return cnt;
		if (check[dislike[x][0]] == 0) {
			q.push(dislike[x][0]);
			check[dislike[x][0]] = 1;
			cnt++;
		}
	}
	return -1;
}

void solve() {
	int ans = bfs(P);
	if (ans == -1) {
		cout << "-1";
	}
	else {
		cout << ans;
	}
}

int main() {
	cin.tie();
	cout.tie();
	cin >> N >> M >> P;
	for (int i = 1; i <= N; i++) {
		int x, y;
		cin >> x >> y;
		dislike[y].push_back(x);
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요