[Programmers] 단어 변환

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

프로그래머스

 

1. Python

from collections import defaultdict, deque


def isAdjacent(word1, word2):
    diff = 0
    for i, c in enumerate(word1):
        if word2[i] != c:
            diff += 1
    return diff == 1


def solution(begin, target, words):
    if target not in words:
        return 0

    if begin not in words:
        words.append(begin)

    N = len(words)
    graph = defaultdict(list)

    for i, word1 in enumerate(words):
        for j in range(i+1, N):
            word2 = words[j]
            if isAdjacent(word1, word2):
                graph[word1].append(word2)
                graph[word2].append(word1)

    q = deque()
    q.append((0, begin))
    visited = set()
    visited.add(begin)
    
    while q:
        t, word = q.popleft()
        if word == target:
            return t
        for neighbor in graph[word]:
            if neighbor not in visited:
                q.append((t+1, neighbor))
                visited.add(neighbor)
    return 0

 

2. C++

#include <string>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
#include <set>

using namespace std;

bool isAdjacent(string word1, string word2) {
	int diff {0};
	for (int i=0; i<word1.size(); i++) {
		if (word1[i] != word2[i]) diff++;
	}
	return diff == 1;
}

int solution(string begin, string target, vector<string> words) {
    if (find(words.begin(), words.end(), target) == words.end()) return 0;
	
	if (find(words.begin(), words.end(), begin) == words.end()) words.push_back(begin);
	
	int n = words.size();
	map<string, vector<string>> graph;
	for (auto word : words) {
		graph[word] = vector<string>();
	}
	
	for (int i=0; i<n; i++) {
		string word1 = words[i];
		for (int j=i+1; j<n; j++) {
			string word2 = words[j];
			if (isAdjacent(word1, word2)) {
				graph[word1].push_back(word2);
				graph[word2].push_back(word1);
			}
		}
	}
	
	deque<pair<int, string>> q;
	q.push_back({0, begin});
	set<string> visited;
	visited.insert(begin);
	
	while (not q.empty()) {
		auto& [t, word] = q.front();
		q.pop_front();
		if (word == target) {
			return t;
		}
		for (auto neighbor : graph[word]) {
			if (visited.find(neighbor) == visited.end()) {
				q.push_back({t+1, neighbor});
				visited.insert(neighbor);
			}
		}
		
	}
	return 0;
}