2644 - 촌수계산

문제

코드

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

int n, x,y, m,a,b,ret,nq;
vector<pair<int,int>> v;
queue<int> q;
int visited[104];
bool flag;

void solve(int z){
	visited[z] = 1;
	q.push(z);
	while(!q.empty()){
		nq = q.front();
		q.pop();
		for(auto it : v){
				if(it.first == nq){
				if(visited[it.second]) continue;
				visited[it.second] = visited[nq] + 1;
				q.push(it.second);
				if(it.second == y){
				flag = 1;
				ret = visited[it.second] - 1;
				break;
				} 
			} 
		}
	}
	if(flag) cout << ret << '\n';
	else cout << -1 << '\n';
}

int main(){
	cin >> n >> x >> y >> m;
	for(int i = 0; i < m; i++){
		cin >> a >> b;
		v.push_back({a,b});
		v.push_back({b,a});
	}
	solve(x);
}

풀이

그래프를 탐색하는데 가중치가 없다 --> BFS로 해야겠다는 생각이 들었다.
처음 너무 생각없이 map으로 설정해서 시간이 조금 걸렸다..ㅋ
연결된 그래프를 입력 받는다.
그래프는 양쪽에서 모두 탐색이 가능하도록 (a,b) (b,a)를 모두 vector에 넣어준다.
기준점은 어느 것이든 상관없지만 찾아야 할 점 중 처음 입력 받은 것을 기준으로 solve 함수를 시작한다.
solve 함수는 BFS로 vector에서 접근 가능한 곳을 하나씩 넣어가며 거리를 구한다. it.first는 부모 it.second는 자식이니 부모를 넣어서 자식을 탐색하고 자식을 넣어 그 자식의 자식을 탐색하며 진행하는데 자식이 입력했던 찾아야할 값이랑 같아지면 flag를 1로 해서 반복문이 끝났을 때 결과를 조건에 맞게 결과를 출력한다.

결과

후기

너무 분야별로 문제를 풀다보니 한쪽으로만 생각하려는 경향이 생긴듯하다.
주어진 조건에서 어떤 것이 최적의 알고리즘일지 생각하는 연습이 필요하다는 생각이 들었다.