[프로그래머스] 단어 변환

링크

https://programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

풀이

 

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 구하는 문제이다.

 

BFS탐색을 이용하여 최소 값을 구하도록 하였고

이전 문자와 다음 문자를 서로 비교하여 다른 부분이 한 개만 있을 때 BFS의 queue에 추가되도록 하여

target 문자열을 만나게 되면 바로 return을 하도록 하였습니다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 55
const int INF = 2000000000;

using namespace std;

typedef long long int ll;

map<char, int> _map[SIZE];

bool word_cmp(string here, string next, int index) {
	int cnt = 0;
	for (int i = 0; i < here.size(); i++) {
		if (here.at(i) == next.at(i))
			cnt++;
	}

	if (cnt == here.size() -1)
		return true;
	else
		return false;
}
queue < pair<string, int> >q;
map<pair<string, string>, bool> visited;

int solution(string begin, string target, vector<string> words) {
	pair<string, int> start(begin, 0);

	int answer = 0;
	q.push(start);
	while (!q.empty()) {
		pair<string, int> h = q.front(); q.pop();

		for (int i = 0; i < words.size(); i++) {
			pair<string, int > n(words[i], h.second + 1);

			if (!word_cmp(h.first, n.first, i)) {
				continue;
			}

			if (visited[make_pair(h.first, n.first)] == true)
				continue;

			if (words[i] == target)
				return n.second;


			q.push(n);
			visited[make_pair(h.first, n.first)] = true;
		}		
	}
	return answer;
}