BOJ (C/C++) 14496번: 그대, 그머가 되어

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

14496번: 그대, 그머가 되어

---

풀이

최소 횟수를 구해야 하므로 BFS를 이용, 탐색하면서 원하는 문자가 나올 경우 해당 지점까지의 바꾼 횟수 반환.큐가 비워졌음에도(모든 노드를 탐색했음에도) 함수가 끝나지 않았을 경우 문자를 바꿀 수 없음 -> -1 반환

 

바꾸려는 문자가 동일한 경우는 예외처리 해줘야 함방문했던 노드는 표기해줘서 여러 번 방문하지 않도록 처리

 

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

queue <pair<int, int>> Q;
vector <int> V[1001];
bool visited[1001];

int BFS(int end) {
	int now, cnt;
	while (!Q.empty()) {

		now = Q.front().first, cnt = Q.front().second;
		Q.pop();
		for (int i : V[now]) {

			// 이미 방문했던 간선 표기
			if (visited[i]) continue;
			visited[i] = true;

			// 원하는 지점에 도달했을 때 방문 횟수 return
			if (i == end) return cnt;
			else Q.push({ i,cnt + 1 });
		}
	}

	// 바꿀 수 없는 경우 -1 return
	return -1;
}
int main() {
	int a, b, N, M, i, j;

	// input
	scanf("%d %d", &a, &b);

	// 바꾸려는 문자가 동일한 경우
	if (a == b) {
		printf("0");
		return 0;
	}

	scanf("%d %d", &N, &M);

	for (int m = 0; m < M; m++) {
		scanf("%d %d", &i, &j);
		V[i].push_back(j);
		V[j].push_back(i);
	}

	// 큐에 시작지점 삽입
	Q.push({ a,1 });
	printf("%d", BFS(b));

	return 0;
}