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

---

 단순히 그래프 순회로 풀 수 있는 문제다. 각 단어를 그래프의 노드라고 보고 변환이 가능한 단어를 인접 노드로 생각한다. 그래서 처음에 문제를 시작할 때 인접 행렬을 생성하고 BFS나 DFS로 선회하면 된다. 

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <iostream>
	using namespace std;
	int adj[51][51];
	bool visited[51];
	queue<pair<int, int>> q;
	bool check(string A, string B) {
	int len = A.length();
	int diff = 0;
	for (int i = 0; i < len; i++) {
	if (A[i] != B[i]) {
	diff++;
	}
	}
	return diff == 1;
	}
	int find(vector<string> words, string target) {
	int idx = -1;
	for (int i = 0; i < words.size(); i++) {
	if (words[i] == target) {
	idx = i;
	break;
	}
	}
	return idx;
	}
	int solution(string begin, string target, vector<string> words) {
	int answer = 0;
	words.insert(words.begin(), begin);
	int size = words.size();
	int target_idx = find(words, target);
	if(target_idx == -1) {
	return 0;
	}
	for (int i = 0; i < size; i++) {
	cout << words[i] << endl;
	for (int j = 0; j < size; j++) {
	adj[i][j] = check(words[i], words[j]);
	}
	}
	q.push({0, 0});
	visited[0] = true;
	while(!q.empty()) {
	int cur = q.front().first;
	int dist = q.front().second;
	q.pop();
	if(cur == target_idx) {
	return dist;
	}
	for (int i = 0; i < size; i++) {
	if (adj[cur][i] != 0 && !visited[i]) {
	q.push({i, dist+1});
	visited[i] = true;
	}
	}
	}
	return 0;
	}

view raw 43163.cpp hosted with ❤ by GitHub