[파이썬, Java] 단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

👸 나의 풀이

 

from collections import Counter
from collections import deque

def solution(begin, target, words):
    dic = {}
    visited=list()
    words.sort()

    for w in words:
        dic[w] = list()
    dic[begin] = list()
	
    # 문자열 비교
    def difference(begin) :
        for w in words :
            temp=(Counter(begin)-Counter(w))
            if len(temp) == 1 :
                dic[begin].append(w)

    difference(begin)	# 시작 문자열에서 변환할 수 있는 문자열 찾기

    for w in words :
        difference(w)	# 리스트 내 문자열끼리 비교

    def bfs(start) :
        idx=0
        que=deque([(start, idx)])	# (문자열, 변환횟수)
        while que :
            char, i=que.popleft()
            if char == target :
                return i+1
            if char not in visited :
                visited.append(char)
                for w in dic[char] :
                    if w not in visited :
                        que.append((w, i+1))

    min_change=0
    
    for begin in dic[begin] :	# 시작 문자열에서 변환할 수 있는 문자열이 여러 개일 때
        result=bfs(begin)
        if result :
            if min_change < result :	# 갱신
                min_change=result
    return min_change

 

bfs 탐색을 하기 전에 각 문자열별로 값이 서로 다른 문자가 1인 문자열을 가지는 딕셔너리를 생성했다.

시작 단어 begin과 리스트 words, words의 문자열 각각 words와 비교를 위해 difference 함수를 만들었다. 

Counter로 문자열에서 각 문자의 갯수를 센 딕셔너리를 생성한다.

-로 w와 비교해 begin에만 있는 문자 딕셔너리를 temp에 담았다.

temp의 길이가 1이면 서로 다른 문자 차이가 1이므로 딕셔너리에 담는다.

시작 문자열 begin에서 변환할 수 있는 문자열이 여러 개일수도 있다. 다 해본뒤 가장 작은 변환 횟수 min_change 반환.

방문한 문자열은 visited에 넣는다.

 

 

import java.util.*;

class Node{
    String word;
    int cnt;

    Node(String word, int cnt){
        this.word=word;
        this.cnt=cnt;
    }
}

class Solution{
    public int solution(String begin, String target, String[] words){
        int cnt=0, k=0;
        String a;
        String b;
        Queue<Node> que=new LinkedList();
        boolean[] visited=new boolean[words.length];
        que.add(new Node(begin, 0));

        while(!que.isEmpty()){
            Node node=que.poll();
            if(node.word.equals(target)){
                return node.cnt;
            }
            for(int i=0; i<words.length; i++){
                if(visited[i]) continue;
                k=0;    // 다른 단어 갯수 카운트
                for(int j=0; j<words[i].length(); j++){
                    a=words[i];
                    b=node.word;
                    if(a.charAt(j) != b.charAt(j)){
                        k++;
                    }
                }
                if(k == 1) {
                    que.add(new Node(words[i], node.cnt+1));
                    visited[i]=true;
                }

            }
        }

        return 0;
    }
}

 

bfs 풀이

다른 사람의 풀이를 보고 이해한 뒤 스스로 다시 작성해봄.

a와 b에 문자열을 넣고 반복문으로 문자 하나씩 비교한다. 서로 다른 문자면 k를 증가시켰다.

 

 

import java.util.*;

class Solution{
    boolean[] visited;
    int ans, k;
    String a;
    public int solution(String begin, String target, String[] words){
        visited=new boolean[words.length];
        ans=0;
        dfs(begin, target, words, 0);
        
        return ans;
    }
    
    public void dfs(String begin, String target, String[] words, int cnt){
        if(begin.equals(target)){
            ans=cnt;
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(visited[i]) continue;
            k=0;    // 서로 다른 문자 갯수 카운트
            a=words[i];
            for(int j=0; j<begin.length(); j++){
                  if (a.charAt(j) != begin.charAt(j)){
                      k++;
                  }
            }
            if(k == 1){
                visited[i]=true;
                dfs(words[i], target, words, cnt+1);  
                visited[i]=false;   
            } 
        }
        
    }
}

 

재귀호출을 이용한 dfs 풀이

 

 

import java.util.*;

class Node{
    String word;
    int cnt;
    
    Node(String word, int cnt){
        this.word=word;
        this.cnt=cnt;
    }
}

class Solution{
    boolean[] visited;
    int ans, k;
    String a;
    public int solution(String begin, String target, String[] words){
        visited=new boolean[words.length];
        LinkedList<Node> stack=new LinkedList<>();
        stack.add(new Node(begin, 0));
        
        while(!stack.isEmpty()){
            Node node=stack.poll();
            if(node.word.equals(target)){
                return node.cnt;
            }
            for(int i=0; i<words.length; i++){
                if(visited[i]) continue;
                k=0;
                for(int j=0; j<node.word.length(); j++){
                    if(node.word.charAt(j) != words[i].charAt(j)){
                        k++;    
                    }
                }
                if(k == 1){
                    stack.add(new Node(words[i], node.cnt+1));
                    visited[i]=true;
                }
            }
        }   
        return ans;
    }    
    }

 

스택을 이용한 dfs 구현

 

 

# 실패
def trans(w, words):
    lst=[0]*len(words)
    idx=0
    for ws in words:
        if ws == w :    # 같은 문자열이면
            idx+=1
            continue
        cnt = 0
        i = 0
        for j in ws:    # 한 문자씩
            if w[i] != j:  # 시작 글자와 words 중 어느 문자와 비교
                cnt += 1
            i += 1
        if cnt == 1:    # 한 글자 차이나면
            lst[idx]=ws
        idx+=1
    return lst

def dfs(v, target, visited, info) :
    answer=0
    if target == info[v][]: 
        return answer
    if visited == 0 :
        visited[v]=1
        dfs(v, target, visited)
        
        
        
    
        
def solution(begin, target, words):
    answer = list()
    words.insert(0, begin)
    length=len(words)
    info=[[]*length for _ in range(length)]
    i=0
    visited=[0]*length
    print(words)
    
    if target not in words :    # target이 없으면
        return 0
    
    # 전처리
    for w in words :
        info[i]=trans(w, words)     # 문자, 문자열 리스트
        i+=1
    #print(info)
    
    for j, i in enumerate(info) :
        print(j, i)
        #if i[0] == 1: 
         #   answer.append(dfs(j, target, visited))
        
    
    return 0  # 변환 불가

#solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])

 

begin과 words 문자열들 각각에 대해 1글자 차이나는 단어를 찾아 info에 담았다.

info에서 행 인덱스는 기준 문자열이다. 값이 0이 아닌 문자열이면 이는 1글자 차이나는 단어다.

dfs로 구현할려고 했는데 코드가 복잡해지고..ㅠ

 

# 실패
answer=0
def dfs(visited, words, begin, target) :
    global answer   
    #stack=begin
    for i in range(len(words)): 
        
        if target == begin:  # target을 찾으면
            return answer
        
        for w in range(0, len(words)) :
            # 한 글자 차이
            if len([j for j in range(0, len(words[w])) if words[w][j] != begin]) == 1 :
                if visited[w] == 0 :
                    visited[w]=1   
                    dfs(visited, words, words[w], target)
        
        answer+=1
                
def solution(begin, target, words):
    global answer
    #words=[begin]+words
    #print(words)
    length=len(words)
    visited=[0]*length
    
    if target not in words :    # target이 없으면
        return 0
    
    dfs(visited, words, begin, target)   
    
    return answer  # 변환 불가

 

나는 재귀로 dfs를 구현할려고 했는데 실패..

최소 변환값을 구할 수가 없네 ㅠ

재귀로 dfs를 구현하는 것은 적절하지 않다는 생각이 들었음.

 

 

👩‍🏫 다른 사람 풀이

 

from collections import deque

transitable=lambda a, b: sum((1 if x!=y else 0) for x, y in zip(a, b))==1
def solution(begin, target, words):
    answer = 0
    d, dic=deque(), {}
    d.append((0, begin))
    # begin에서 변환할 수 있는 단어 찾기
    dic[begin]=set(filter(lambda x: transitable(x, begin),words ))	
    
    # words 단어들 각각이 변환될 수 있는 단어 찾기
    for w in words:
        dic[w]=set(filter(lambda x: transitable(x, w), words))
    
    while d:
        idx, value = d.popleft()	# idx : 변환 횟수, value : 문자열
        if idx==len(words):
            return 0
        for v in dic[value]:
            if v == target:
                return idx+1
            else:
                d.append((idx+1, v))
    return answer

 

deque와 딕셔너리, bfs를 이용한 풀이.

딕셔너리에 key를 문자로 하고 값은 key가 변환 될 수 있는 문자열을 넣는다.

 

 

# 출처 : https://khann.tistory.com/79
answer=0
def dfs(begin, target, words, visited) :
    global answer
    stacks=[begin]
    
    while stacks :
        # 스택을 활용한 dfs 구현
        stack=stacks.pop()
        
        if stack == target :
            return answer
        
        for w in range(0, len(words)) :
            # 조건 1. 한 개의 알파벳만 다른 경우
            if len([i for i in range(0, len(words[w])) if words[w][i] != stack[i]]) == 1:
                if visited[w] != 0 :	# 방문한 적 있으면
                    continue
                
                visited[w]=1
                
                # stack에 추가
                stacks.append(words[w])
                
        answer+=1	# 변환횟수
        
def solution(begin, target, words) :
    global answer
    
    # 조건 2. words에 있는 단어로만 변환할 수 있습니다.
    if target not in words :
        return 0
    
    visited=[0 for i in words]
    
    dfs(begin, target, words, visited)
    
    return answer

 

스택에 시작값으로 begin을 넣는다.

stack에 값이 있을 동안에 반복문을 돌린다.

stack에서 값을 빼서 target과 비교한다. 일치하면 answer을 리턴한다.

stack은 words의 모든 문자열들과 비교하게 된다. 서로 다른 문자가 1개인지 확인한다.

방문한 적 없고(visited[w] == 0) 한 개의 알파벳만 다르면 방문 처리하고, stack에 추가한다.

 

def solution(begin, target, words):
    answer = 0
    Q = [begin]

    while True:
        temp_Q = []
        for word_1 in Q:
            if word_1 == target:
                    return answer
            for i in range(len(words)-1, -1, -1):
                word_2 = words[i]
                if sum([x!=y for x, y in zip(word_1, word_2)]) == 1:
                    temp_Q.append(words.pop(i))

        if not temp_Q:
            return 0
        Q = temp_Q
        answer += 1

 

stack을 이용한 dfs

 

 

// https://velog.io/@hammii/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98-java
import java.util.*;
class Solution {
    static boolean[] visited;
    static int answer=0;
    
    public int solution(String begin, String target, String[] words) {
        visited=new boolean[words.length];
        
        dfs(begin, target, words, 0);

        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt){
        if(begin.equals(target)){
            answer=cnt;
            return;
        }
        
        for(int i=0; i<words.length; i++){
            if(visited[i]){
                continue;
            }
            
            int k=0;    // 같은 스펠링 몇 개인지 세기
            for(int j=0; j<begin.length(); j++){
                if(begin.charAt(j) == words[i].charAt(j)){
                    k++;
                }
            }
            
            if(k == begin.length()-1){  // 한 글자 빼고 모두 같음
                visited[i]=true;
                dfs(words[i], target, words, cnt+1);
                visited[i]=false;
            }
        }
    }
}

 

재귀호출을 이용한 dfs

visited가 true인 단어는 건너띄고, charAt으로 한 글자씩 비교한다.

한 글자만 다르면 visited를 true 처리하고 재귀호출한다.

더 이상 단어를 변환하지 못하면 visited를 다시 원래대로 돌려놓는다.

false로 돌려놓은 단어와 begin을 비교한다.

 

 

// https://maetdori.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98-JAVA
import java.util.*;

class Node{
    String word;
    int cnt;
    
    Node(String word, int cnt){
        this.word=word;
        this.cnt=cnt;
    }
}

class Solution{
    public int solution(String begin, String target, String[] words){
        Queue<Node> queue=new LinkedList<>();
        boolean[] visited=new boolean[words.length];
        
        queue.offer(new Node(begin, 0));
        
        while(!queue.isEmpty()){
            Node node=queue.poll();
            
            if(node.word.equals(target)){
                return node.cnt;
            }
            
            for(int i=0; i<words.length; i++){
                if(visited[i]) continue;
                if(changeable(node.word, words[i])){
                    queue.offer(new Node(words[i], node.cnt+1));
                    visited[i]=true;
                }
            }
        }
    return 0;
    }
    
    private boolean changeable(String from, String to){
        int diff=0;
        
        for(int i=0; i<to.length(); i++){
            if(from.charAt(i) != to.charAt(i))
                diff++;
        }
        
        if(diff == 1) return true;
        return false;
    }
}

 

bfs로 구현

단어, 변환횟수를 담은 class Node를 만들었다.

changeable 메소드에서 from과 to가 한 글자 차이면 true를 리턴하고, 큐에 추가한다.

 

 

 

💁‍♀️ 문제 출처 : 프로그래머스