BOJ 10552번: DOM

그래프를 활용해서 풀면 된다.

 

싫어하는 채널 -> 좋아하는 채널 방향으로 간선이 있는 것으로 표시하고, 사이클이 형성된다면 -1을 리턴해야한다.

 

** 채널을 바꾼 사람이 다시 움직인다면 사이클이 형성된 것으로 볼 수 있다. (처음에 이부분에서 실수)

 

visited 배열으로 움직인 사람을 체크해서 사이클이 형성되었는지 확인할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100000 + 2;

int N, M, P; //사람 수, 채널 수, 현재 채널
vector<int> channel[MAX];
bool visited[MAX];

int change() {
	queue<int> q;
	q.push(P);
	visited[P] = true;
	int cnt = 0;

	while (!q.empty()) {

		int cur = q.front();
		q.pop();

		if (channel[cur].size() == 0) {
			return cnt;
		}
		if (visited[channel[cur][0]]) {
			break;
		}
		q.push(channel[cur][0]);
		visited[channel[cur][0]] = true;
		cnt++;

	}
	return -1;
}

int main() {
	int N;
	scanf("%d %d %d", &N, &M, &P);

	for (int i = 0; i < N; i++) {
		int like, hate;
		scanf("%d %d", &like, &hate);
		channel[hate].push_back(like);
	}

	printf("%d\n", change());

	return 0;
}