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

2016/02/01 20:13

상파

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

8개의 풀이가 있습니다.

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

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

2016/03/29 13:11

룰루랄라

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- 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;  
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import random

_dict = ['hot','dot','dog','lot','log']
result_list = list()
for z in range(len(_dict)*len(_dict)-1):
    start,end,x = 'hit','cog',0
    result = [start]
    a = list()
    while start != end:
        if not x in a:
            tmp = list(start)
            tmp[x] = chr(random.randint(97,122))
            tmp = ''.join(tmp)
            if tmp in _dict and not tmp in result or tmp == end:
                start = tmp
                result.append(tmp)
                if tmp[x] == end[x]:
                    a.append(x)
        if x == len(tmp)-1:
            x = 0
        else:
            x += 1
    if not result in result_list:
        result_list.append(result)
result_list = sorted(result_list)
length = len(result_list[0])
for z in result_list:
    if len(z) == length:
        print(z)

#### 2017.01.28 D-390 ####

다른분들에 비해 좀 어설퍼보입니다.. 그냥 풀어버린다!! 이런마음이 강하네요 ㅠ

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

Python: Dijkstra

def adjacent(word1, word2):  # 한 글자만 다르니?
    d = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            d += 1
    return d == 1

start = "hit"
end = "cog"
M = 1000000 # 막막 큰 숫자
V = {start:1, "hot":M, "dot":M, "dog":M, "lot":M, "log":M, end:M}  # 방문하지 않은 단어들

while V:
    (v, path) = min(V.items(), key = lambda x: x[1]);  # V 안에서 value가 가장 작은 (key, value)
    V.pop(v)
    if v is end:
        print(path);
        break

    for word in V:
        if adjacent(v, word) and path + 1 < V[word]:
            V[word] = path + 1

파이썬 너무 멋진 듯.

.

.

모든 경로 출력(BFS):

(어라 이게 더 간단한ㅋㅋ 이리저리 재는 거보다 경로를 그냥 때려박는 게 더 쉽네요 허허)

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

dic += [end]
Q = [[start]]   # 경로들을 저장하는 큐
S = []          # 현재까지 최단경로"들"

while Q:
    path = Q.pop(0)
    if path[-1] is end:
        if not S or len(path) < len(S[0]):
            S = [path]
        elif len(path) == len(S[0]):
            S += [path]
    else:
        for word in dic:
            if word not in path and adjacent(path[-1], word):
                Q.append(path + [word])

for path in S:
    print('->'.join(path))

.

.

그리고 난잡한 C# 코드:

시험삼아 여러가지로 삽질해 보다가 그냥 그래프로 작성했는데 고수 분들이 보면 고칠 데가 많을 거 같습니다.

OOP 어렵다 으어어


using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Vertex : IComparable<Vertex>
{
    public string name { get; set; }
    public int distance { get; set; }

    public Vertex(string name, int distance)
    {
        this.name = name;
        this.distance = distance;
    }

    public int CompareTo(Vertex v)
    {
        return this.distance - v.distance;
    }

    public bool AdjacentTo(Vertex other)
    {
        int d = 0;
        for (int i = 0; i < this.name.Length; i++)
        {
            if (this.name[i] != other.name[i])
            {
                d++;
            }
        }
        return d == 1;
    }
}

class UndirectedEdge : IEquatable<UndirectedEdge>
{
    public Vertex u { get; set;}
    public Vertex v { get; set; }

    public UndirectedEdge(Vertex u, Vertex v)
    {
        this.u = u;
        this.v = v;
    }

    public bool Equals(UndirectedEdge other)
    {
        return this.u.name == other.u.name && this.v.name == other.v.name ||
            this.u.name == other.v.name && this.v.name == other.u.name;
    }
}

class UndirectedGraph
{
    public List<Vertex> V { get; set; }
    public List<UndirectedEdge> E { get; set; }

    public UndirectedGraph()
    {
        this.V = new List<Vertex>();
        this.E = new List<UndirectedEdge>();
    }
}

class WordLadder
{
    static void Main(string[] args)
    {
        string start = "hit", end = "cog";
        string[] dict = { "hit", "hot", "dot", "dog", "log", "log", "cog" };

        // setup
        UndirectedGraph G = new UndirectedGraph();
        foreach (string word in dict)
        {
            G.V.Add(new Vertex(word, word == start ? 1 : 1000000));
        }
        foreach (var u in G.V)
        {
            /*
             from ~ in ~ where ~ select 순서 정확해야 해서 불편함. 근데 왜 안되는지 모르겠네-_-;
            G.E = (from v in G.V
                   where u.AdjacentTo(v)
                   select new UndirectedEdge(u, v)
                   ).ToList<UndirectedEdge>();
            */
            foreach (var v in G.V)
            {
                if (u.AdjacentTo(v))
                {
                    G.E.Add(new UndirectedEdge(u, v));
                }
            }
        }

        // Dijkstra
        List<Vertex> notVisited = G.V.ToList<Vertex>();

        while (notVisited.Count > 0)
        {
            Vertex u = notVisited.Min();
            notVisited.Remove(u);

            if (u.name == end)
            {
                WriteLine(u.distance);
                break;
            }

            foreach (var v in notVisited)
            {
                if (G.E.Exists(e => e.Equals(new UndirectedEdge(u, v))) &&
                    u.distance + 1 < v.distance)
                {
                    v.distance = u.distance + 1;
                }
            }
        }
    }
}

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

풀이 작성

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

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

queue x 2
BFS x 1
연관 문제
DARK4Hoon, 2017/08/12 18:08

언어별 풀이 현황
전 체 x 8
python x 5
php x 1
ruby x 1
cpp x 1