[프로그래머스] 단어변환

 

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

프로그래머스

---

[풀이]

전형적인 DFS와 Backtracking을 활용한 문제이다.

먼저 논리의 순서대로 해보자면

 

(1) target이 words리스트에 있는지/ 없는지를 확인해야한다.

=> 있다면 dfs()함수를 호출하여 target까지 도다하는데 최소 횟수를 구해야한다.

=> 없다면 0을 리턴한다.

 

target이 words 리스트에 존재한다면

(2) words의 모든 원소들에 대한 방문리스트를 나타낸다.

나는 여기서 방문리스트를 딕셔너리를 이용하여 나타냈다.

words=['cat', 'hat', 'hot'] 이라면 visited['cat']=0 이런 식으로 말이다.

visited[key값]=0 은 아직 방문하지 않은 상태를

1은 이미 방문한 상태를 의미한다.

 

(3) dfs를 실행한다.

dfs를 실행할때 조건을 두갈래로 나눌 수있다.

- now(현재단어)가 target과 같다

- now가 target과 같지 않다.

 

-now가 target과 같다면 => target까지 도달할때까지 최소방문횟수를 구한다.

-now가 target과 같지 않다면

[조건1]=> words 리스트의 원소가 아직 방문하지 않은 상태이고(visited[word]=0)

[조건2]=> words의 원소(word)와 now의 글자수 차이가 1이어야한다.

문제 조건은 "words에 있는 단어로 변환할 수 있다"와 "한개의 알파벳만 바꿀 수 있다"이기 때문이다.

 

=> [조건1]과 [조건2]를 만족하는 원소가 2개이상일 때 visited는 따로 해야한다.

예를 들어서 설명하자면..

now='hit'이고 두 조건을 만족하는 원소가 'dit'와 'kit'가 있을 때

반복문을 하게되면 dit와 kit가 모두 방문하게되므로

이러한 오류를 막기위해서 기존 방문리스트(visited)를 복사했다.

dfs( word='dit', target, words, cnt+1, copy_visited={'dit':1, 'kit':0})

dfs( wrod='kit', target, words, cnt+1, copy_visited={'dit:0, 'kit':1

---

[코드 python3]

import sys
from copy import copy
sys.setrecursionlimit(10**6)
min_cnt=51

def count_diff(now, word):
    cnt=0
    for n,w in zip(now, word):
        if n!=w:
            cnt+=1
    return cnt

def dfs(now, target, words, cnt, visited):
    global min_cnt
    if now==target:
        min_cnt=min(min_cnt, cnt)
    
    for word in words:
        if(count_diff(now, word)==1) and(visited[word]==0):
            tmp=copy(visited)
            tmp[word]=1
            dfs(word, target, words, cnt+1, tmp)
            

def solution(begin, target, words):
    global min_cnt
    if target not in words:
        return 0
    
    visited=dict()
    for word in words:
        visited[word]=0
    
    dfs(begin, target, words, 0, visited)
    return min_cnt

---

[백준버젼 코드]

import sys
from copy import copy
input=sys.stdin.readline
sys.setrecursionlimit(10**8)
min_cnt=51

def count_diff(now, word):
    cnt=0
    for n, w in zip(now, word):
        if n!=w:
            cnt+=1
    return cnt

def dfs(now, target, words, cnt, visited):
    global min_cnt

    #now가 target과 같은가?
    if now==target:
        min_cnt=min(min_cnt, cnt)
        
    #now와의 차이가 1개인가?
    for word in words:
        if (count_diff(now, word)==1) and (visited[word]==0):
            tmp=copy(visited) #방문리스트를 복사한다.
            tmp[word]=1
            dfs(word, target, words, cnt+1, tmp)

def solution(begin, target, words):
    global min_cnt
    # target이 words에 없는가? -> 0 리턴
    if target not in words:
        return 0

    #방문리스트 초기화
    visited=dict()
    for word in words:
        visited[word]=0
        
    # target이 words에 있다면..
    dfs(begin, target, words, 0, visited)
    return min_cnt
    
def main():
    begin=input().strip()
    target=input().strip()
    words=input().strip().split(',')
    return solution(begin, target, words)

if __name__=='__main__':
    print(main())