Word Ladder

출처 : http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

시작단어와 목표단어가 주어집니다. 시작단어에서 한글자씩 임의로 바꿀 수 있습니다. 단, 그 단어는 주어진 사전에 있어야 하는 단어입니다.

가장 짧은 경로를 찾았을 때 거쳐간 단어수를 출력하세요

아래 예에서 가장 짧은 경로는 "hit" -> "hot" -> "dot" -> "dog" -> "cog" 이므로 프로그램은 시작부터 목표까지 총 거쳐간 단어수 '5'를 출력해야합니다.

다음을 프로그램내에서 정의하시고

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

출력은

5

도전과제 : 최단거리와 같은 모든 경로를 출력하시오

hit hot dot dog cog
hit hot lot log cog
queue BFS
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

6개의 풀이가 있습니다.

평범하게(?) 그래프를 이용해서 풀어보았습니다.

dic = ['hot', 'dot', 'dog', 'lot', 'log', 'cog', 'hit', 'hog']

class Node:
    def __init__(self, word):
        self.word = word
        self.neighbors = []
        self.keys = set()
        self.color = 'white'
        self.totalDist = -1
        self.successor = None
        self.precedessor = None
        for i in range(len(word)):
            key = word[:i] + '_' + word[i+1:]
            self.keys.add(key)

    def addNeighbor(self, node):
        if self.keys.intersection(node.keys):
            self.neighbors.append(node)

    def __repr__(self):
        return self.word


class Graph:
    def __init__(self, words=None):
        self.vertices = []
        if words:
            self.build(words)

    def build(self, words):
        for word in words:
            aNode = Node(word)
            self.vertices.append(aNode)
        for a in self.vertices:
            for b in self.vertices:
                if a is not b:
                    a.addNeighbor(b)
                    b.addNeighbor(a)

    def run(self, startWord):
        sNode = self.find(startWord)
        if sNode:
            sNode.totalDist = 1
            return self.runHelper(sNode)
        return -1

    def find(self, word):
        sNodes = [x for x in self.vertices if x.word == word]
        if sNodes:
            return sNodes[0]
        print('there is no "%s"' % word)
        return None

    def runHelper(self, cn):
        minDist = cn.totalDist
        cn.color = 'black'
        for n in [x for x in cn.neighbors]:
            if n.totalDist == -1 or cn.totalDist + 1 < n.totalDist:
                n.precedessor = cn
                cn.successor = n
                n.totalDist = cn.totalDist + 1
                self.runHelper(n)
        return minDist


g = Graph(dic)
print(g.vertices)
g.run('hit')
dest = g.find('cog')
print(dest.totalDist)
start = g.find('hit')
while True:
    print(start)
    if start is dest:
        break
    start = start.successor
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- coding: utf-8 -*-
#http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

start = "hit"
end = "cog"
dic = ["hot","dot","dog","lot","log"]

def isOneLetterDifferent(a,b):#한글자만 다른지 검사함
    if len(a)!=len(b) or len(a)*len(b)==0 or a==b: return False
    while a[0]==b[0]: a=a[1:];b=b[1:] #앞쪽 글자가 같으면 다 잘라냄
    while a[-1]==b[-1]: a=a[:-1];b=b[:-1] #뒤쪽 글자가 같으면 다 잘라냄
    if len(a)==len(b)==1 : return True #잘라내고 남은 글자수가 둘다1글자면 '그래'출력'
    else : return False #'아냐' 출력
def wordLadder(start,end,dic):
    q=[[start]] #큐에는 단어가 변해갈때 그 경로가 모두 리스트로 저장
    res=[]
    shortest_length = len(dic)+2
    while q:
        w = q.pop(0) 
        if len(w)+1> shortest_length :continue #최단 코스보다 긴것들은 걸러냄. +1은 
                                                #end를 더했을경우를 상정
        for word in [end]+dic:
            if isOneLetterDifferent(word,w[-1]):
                if word == end :
                    if len(w)+1 <= shortest_length:
                        shortest_length = len(w)+1
                        res.append(w+[end])
                elif not word in w : q.append(w+[word]) #반복되는 경로는 제외
    return res,shortest_length

print wordLadder(start,end,dic)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
start = "hit"
end = "cog"
dictionary = ["hot","dot","dog","lot","log"]
def onechanged(A, B):
    changed = 0
    for x, y in zip(A, B):
        if x != y:
            changed+=1
    if changed == 1:
        return True
    else:
        return False

def find(previous = start, history = [start], depth = 0):
    if depth == 3:
        if end not in history and onechanged(end, previous):
            print(history+[end])
    else:
        for x in (list(set(dictionary)-set(history))):
            if onechanged(x, previous):
                find(x, history+[x], depth+1)

if __name__ == '__main__':
    find()

파이썬 3.5.1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

PHP로 한번 만들어 봤습니다.

  1. 마지막이 cog가 되는 전체의 경우의 수를 배열로 저장
  2. 계산 하기 쉽게 배열 재정의
  3. 최단 거리만 남겨두고 나머진 다 삭제
  4. 출력
<?php
$start = "hit";
$end = "cog";
$dict = ["hot","dot","dog","lot","log"];

$graph_arr[$start] = graphArr($start,$end,$dict);
$dot = dot($graph_arr);
$list = del($dot);

foreach ($list as $key => $val) {
    echo $val."\n";
}

#최단거리 아닌얘들 삭제
function del($array)
{
    $tmp = array();
    foreach ($array as $key => $val) {
        $len = strlen($val);
        $tmp[$len][] = $val;
    }

    ksort($tmp);

    $mins = array();
    foreach ($tmp as $key => $val) {
        $mins = $val;
        break;
    }
    return $mins;
}

#dot찍기
function dot($array, $prepend = '')
{
    $results = [];
    foreach ($array as $key => $value) {
        if (is_array($value) && ! empty($value)) {
            $results = array_merge($results, dot($value, $prepend.$key.'.'));
        } else {
            $results[] = $prepend.$key.'.'.$value;
        }
    }
    return $results;
}

#graph생성
function graphArr($start,$end,$dict)
{
    $start_arr = strArr($start);
    $end_arr = strArr($end);

    $arr = array();
    foreach ($dict as $key => $val) {
        $tmp_dict = $dict;
        $val_arr = strArr($val);

        if(strTwoCheck($start_arr,$val_arr)){
            unset($tmp_dict[$key]);
            $arr[$val] = graphArr($val,$end,$tmp_dict);
            if(strTwoCheck($end_arr,$val_arr)){
                $arr[$val] = $end;
                break;
            }
        }
    }

    return $arr;
}

exit;

결과

hit.hot.dot.dog.cog
hit.hot.lot.log.cog
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

두 가지 풀이.

nexts = ->word,dict { dict.select {|w| (word.chars-w.chars).size==1 } }
laddr = ->dict,word,path { path[-1] == dest ? {path*' ' => path.size} :
                           nexts[word,dict].map {|e| laddr[dict-[e],e,path+[e]] } }
w_laddr = ->s,d,dict { v = laddr[dict<<d,s,[s]].flatten.reduce :merge
                       min = v.values.min; [min, v.select{|_,v|v==min}.keys] }

or

s_path = Hash.new{|hsh,key| hsh[key] = [] }
nexts = ->word,dict { dict.select {|w| (word.chars-w.chars).size==1 } }
laddr = ->dict,word,path { path[-1] == dest ? s_path[path.size].push(path*' ') :
                           nexts[word,dict].each {|e| laddr[dict-[e],e,path+[e]] } }
w_laddr = ->s,d,dict { laddr[dict<<d,s,[s]]; s_path.min }

Test

start, dest = %w(hit cog); dict = %w(hot dot dog lot log)
expect(w_laddr[start, dest, dict]).to eq [5, ["hit hot dot dog cog",
                                              "hit hot lot log cog"]]

Output

#=> puts w_laddr[start, dest, dict]
5
hit hot dot dog cog
hit hot lot log cog
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C++입니다. bfs로 가장 짧은 경로의 길이를 출력합니다.

#include <iostream>
#include <cstdio>  
#include <cstdlib>
#include <string> 
#include <algorithm> 
#include <vector> 
#include <map> 
#include <set> 
#include <queue> 
using namespace std; 

typedef pair<string,int> P; 

int main(){
    vector<string> dict; 
    dict.push_back("hot");  
    dict.push_back("dot"); 
    dict.push_back("dog"); 
    dict.push_back("lot"); 
    dict.push_back("log");  
    string start = "hit",end = "cog"; 
    dict.push_back(end); 
    queue<P> que; 
    que.push(P(start,1));   
    map<string,bool> visited; // 도착했는지 확인여부. 
    visited[start] = true; 
    while (!que.empty()){
        P p = que.front(); que.pop(); 
        string word = p.first; 
        int step = p.second; 
        if (word == end){
            cout << step << endl; 
            break; 
        }
        for (int i = 0; i < word.size(); i++){
            for (char c = 'a'; c <= 'z'; c++){
                char temp = word[i]; 
                string orig = word;  
                if (word[i] != c) word[i] = c; 
                if (find(dict.begin(),dict.end(),word) != dict.end() && !visited[word]){
                    visited[word] = true;  
                    que.push(P(word,step+1));  
                }
                word[i] = temp; 
            }
        }
    }
    return 0;  
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

queue x 2
BFS x 1
연관 문제
김 영현, 2017/01/15 20:15

언어별 풀이 현황
전 체 x 6
python x 3
cpp x 1
php x 1
ruby x 1