[백준/c++] BOJ 14496 - 그대, 그머가 되어

https://www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

 

문제 설명

머호는 문자 a를 문자 b로 바꾸려고 한다.

N개의 문자와 치환 가능한 M개의 문자쌍이 있을 때, a를 b로 바꾸기 위한 치환의 최소 횟수를 구한다.

치환이 불가능한 경우는 -1를 출력한다.

N (1 <= N <= 1,000)

M (1 <= M <= 10,000)

 

해결

간단한 bfs 문제이다.

 

vector에 치환 가능한 문자열을 넣어 주고, 시작 문자 a로부터 모든 치환 가능한 문자들을 방문하며 b가 될 때까지 bfs를 돈다.

queue 안에는 현재 문자만 넣어 주고, 시간은 visited 배열의 숫자를 증가시켜 계산해 주었다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int a, b, c, d;
int n, m;
int visited[1001];
vector<int> v[1001];

int bfs() {
	queue<int> q;
	q.push(a);
	visited[a] = 1;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < v[cur].size(); i++) {
			if (visited[v[cur][i]]) continue;
			if (v[cur][i] == b) return visited[cur];
			visited[v[cur][i]] = visited[cur] + 1;
			q.push(v[cur][i]);
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> a >> b;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> c >> d;
		v[c].push_back(d);
		v[d].push_back(c);
	}

	if (a == b) {
		cout << 0;
		return 0;
	}
	cout << bfs();
}