개요

백준 10552번: DOM

• 입력
  The first line of input contains three integers N, M and P (1 ≤ N, M ≤ 105, 1 ≤ P ≤ M), the number of pensioners, the number of TV channels and the initial channel displayed on TV.

  Each of the following N lines contains two integers ai and bi (1 ≤ ai, bi ≤ M, ai ≠ bi), the favourite and hated channel of each pensioner.

  The ordering of pensioners in the input is from the youngest to the oldest.

• 출력
  The first and only line of output must contain the required number of channel changes. If the changes continue indefinitely, output -1.

접근 방법

1. 처음엔 어떻게 접근할지 고민하다가 예제 2번을 보고 방향 그래프 문제인걸 깨달았다.
   싫어하는 채널이 나오면 좋아하는 채널로 변경한다.
   싫어하는 채널(노드) -> 좋아하는 채널(노드)
2. 싫어하는 채널이 겹칠 경우 입력값 순서대로 변경이 아니라
   제일 어린녀석 한명만 변경한다.
   -> 하나의 노드가 무조건 하나의 노드를 가리키는 방향 그래프다.
3. 인접노드가 다 1개씩이므로 방문여부를 배열로 체크한 후,
   방문한적있는 노드를 다시 방문시 무조건 싸이클 형성하게되므로
   -1을 출력하면 된다.

코드

#include<iostream>
#include<vector>

using namespace std;

int pensioners=0, channels=0, initChannel=0,channelChangedNum=0;
vector<int> adj;
vector<bool> visited;

void input() {
	int fromNode = 0, toNode = 0;
	cin >> pensioners >> channels >> initChannel;
	adj.resize(channels+1);
	visited.resize(channels+1);
	fill(visited.begin(), visited.end(), false);
	
	for (int i = 0; i < pensioners; i++) {
		cin >> toNode >> fromNode;
		//한 노드가 가리키는노드는 무조건 하나이므로 
		if (adj[fromNode] == 0)
			adj[fromNode] = (toNode);
		//이미 입력된 노드면 무시한다.
		else
			continue;
	}
}

void dfs(int Node) {
	//해당 노드에서 연결된게 없으면 채널 모두가 만족
	if (adj[Node]==0) return;
	//만약 방문한 채널이 아니라면
	if (!visited[adj[Node]]) {
		//방문 체크
		visited[adj[Node]] = true;
		//싸이클이 아닌경우
		if (channelChangedNum != -1) {
			//채널 바꾼 수 +1
			channelChangedNum++;
			//다음 노드값 dfs함수 시행
			dfs(adj[Node]);
		}
	}
	//방문한 채널을 또 방문하면 무조건 싸이클이므로 
	else {
		//싸이클일땐 -1로 저장
		channelChangedNum = -1;
	}
}

void solution() {
	dfs(initChannel);
	cout << channelChangedNum;
}

int main() {
	input();
	solution();

}

문풀후생

그래프에 안 익숙해서 그런지 싫어하는 채널에서 좋아하는 채널로 돌린다.
에서 바로 방향 그래프문제임을 캐치하지 못했다.

예제 2번에서 -1이 나오는걸 보고 싸이클? 오 그래프 이런식으로 떠올려서
알게되었다.