단어 변환

단어 변환

2019, Jun 02    
  • https://programmers.co.kr/learn/courses/30/lessons/43163
  • 인접리스트를 잘 만들면 풀 수 있는 문제입니다.
  • 주어진 단어 리스트들 중에서 한 단어만 다른 단어들이 서로 연결되어 있는 노드입니다.
  • 한 단어만 다른 단어들을 인접리스트에 추가한 뒤 BFS를 이용하여 최단 거리를 구하면 문제를 해결할 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> dist;
vector<int> adjList[55];

int countDiff(string& s1, string& s2) {
	int cnt = 0;
	for (int i = 0; i < s1.size(); ++i) {
		if (s1[i] != s2[i]) {
			cnt++;
		}
	}
	return cnt;
}

int solution(string begin, string target, vector<string> words) {
	int answer = 99999999;
		
	// begin에 해당하는 단어를 words에 추가
	words.push_back(begin);

	// 노드의 시작과 끝을 확인
	int start = words.size() - 1;
	int end = find(words.begin(), words.end(), target) - words.begin();

	if (end != words.size()) {

		// 각 단어 끼리 모두 비교하여 단어간 차이가 1이면 adjList 추가
		for (int i = 0; i < words.size(); ++i) {
			for (int j = i + 1; j < words.size(); ++j) {
				if (countDiff(words[i], words[j]) == 1) {
					adjList[i].push_back(j);
					adjList[j].push_back(i);
				}
			}
		}

		queue<int> q;
		dist = vector<int>(words.size(), -1);
		q.push(start);
		dist[start] = 0;

		while (!q.empty()) {
			int here = q.front();
			q.pop();

			for (int i = 0; i < adjList[here].size(); ++i) {
				int there = adjList[here][i];
				if (dist[there] == -1) {
					q.push(there);
					dist[there] = dist[here] + 1;
				}
			}

		}

		answer = dist[end];
	}
	else {
		answer = 0;
	}

	return answer;
}