백준14496 그대, 그머가 되어

작성일 | In

문제 링크

  • http://icpc.me/14496

문제 출처

  • 2017 선린 봄맞이 대회 J번

사용 알고리즘

  • BFS

시간복잡도

  • O(n + m)

풀이

문자를 정점으로 두고, 치환 가능한 문자끼리 간선으로 이어주면 그래프가 됩니다.
그래프로 모델링을 해주면 치환의 최소 횟수는 그래프 상에서 최단 경로임을 알 수 있습니다.
비가중치 그래프이므로 BFS를 해주면 O(n + m)만에 최단 경로를 찾을 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p; //node depth

int a, b, n, m;
int arr[1010][1010];
int visit[1010];
int bfs(){
	queue<p> q;
	q.push(make_pair(a, 0));
	visit[a]=1;
	while(!q.empty()){
		p poped=q.front();
		q.pop();
		if(poped.first == b) return poped.second;
		for(int i=1; i<=n; i++){
			if(!visit[i] && arr[poped.first][i]){
				q.push(make_pair(i, poped.second+1));
				visit[i]=1;
			}
		}
	}
	return -1;
}

int main(){
	scanf("%d %d %d %d", &a, &b, &n, &m);
	for(int i=0; i<m; i++){
		int as, df;
		scanf("%d %d", &as, &df);
		arr[as][df]=1;
		arr[df][as]=1;
	}
	printf("%d", bfs());
}