문제

나의 요약

사람들에 대한 부모 자식 간의 관계가 주어졌을 때, 두 사람의 촌수 계산하자.

접근 방식

가계도처럼 사람을 연결해야하니, 딱 봐도 그래프를 활용해야 하는 문제처럼 보였다.
생각해보면 DFS나 BFS나 어느 방법으로 탐색을 해도 결국 답은 찾을 수 있을 것이라고 생각했다. 내가 조금 더 좋아하는 DFS로 풀어보기로 했다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N;
int a, b;
vector<vector<int> > adj;

void Input()
{
	cin >> N;
	for(int i = 0; i < N; i++)
	{
		vector<int> v;
		adj.push_back(v);
	}
	
	cin >> a >> b;
	a--; b--;
	
	int M;
	cin >> M;
	for(int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		x--; y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
}

void Solve(int start)
{
	// Node, Chon
	stack<pair<int, int> > st;
	vector<bool> visited;
	visited.assign(N, false);
	st.push({start, 0});
	
	int chon = -1;
	while(!st.empty())
	{
		int now = st.top().first;
		int nowChon = st.top().second;
		st.pop();
		
		if(visited[now]) { continue; }
		visited[now] = true;
		
		if(b == now)
		{
			chon = nowChon;
			break;
		}
		
		for(int i = 0; i < adj[now].size(); i++)
		{
			int next = adj[now][i];
			if(!visited[next])
			{
				st.push({next, nowChon+1});
			}
		}
	}
	
	cout << chon;
}

int main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cout.tie(NULL);
  	
  	Input();
  	Solve(a);
}

stack 자료 구조를 이용한 DFS 방식으로 풀었다. 중요한 점은 stack<pair<int, int>> 형을 통해 노드의 번호와, 현재 몇 촌인지를 같이 저장하는 것이다. 바로 붙어있는 인접노드들은 무조건 부모/자식 관계이기 때문에 당사자의 촌보다 +1이 된다. 이 점에 유의해 DFS를 진행하다가, 우리가 찾으려고 하는 타겟 노드를 발견하면 저장하고 멈추면 된다.

물론 못 찾는 경우엔 초기값으로 저장된 -1이 그대로 유지되니 별다른 처리를 할 필요는 없다.

헤맨 지점

visited.assign(N, false); 부분에서 개수와 초기값의 인자 위치를 헷갈렸던 것 빼고는 별달리 어려운 점이 없었다. 다음부터는 너무 빠르게 풀었다고 생각이 들면 다음 난이도의 문제를 풀어봐야겠다.