[Python3]프로그래머스_단어변환
문제출처: https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3
접근법
아이디어가 어렵다기 보다는 구현에서 조금 애를 먹었다.
mutable object( list )는 call by reference가 기본이므로 원하는대로 dfs가 이루어지지 않았다.
=> new = v[:] 와 같이 다른 객체로 복사하여 해결
- words 배열 중 방문하지 않은 word를 현재의 단어(current)와 비교하여 한글자만 다른 word를 찾는다.( dif == 1 )
- 찾은 word를 방문했음을 표시하고 현재의 단어를 word로 변경하여 재귀호출
- 종료조건: 현재의 단어(current)가 target과 같아짐 또는 모든 word를 방문한 케이스인 경우
- answer = min(answer,count) or count 의 경우
초기값이 0일때는 False이므로 count를 할당하고
값이 있는 경우 True이므로 min(answer,count)를 할당한다.
코드
answer = 0
def solution(begin, target, words):
global answer
v = [0] * len(words)
def dfs(current,count,v):
global answer
new = v[:]
if( current == target ): # target과 같아지면
answer = min(answer,count) or count
return
for i,word in enumerate(words):
if( new[i] == 0 ): # 방문하지 않은 word
dif = 0
for j in range(len(begin)): # 한 글자만 다른지 확인
if( current[j] != word[j] ):
dif += 1
if( dif == 1 ): # 한 글자만 다르다면
new[i] = 1
dfs(word,count+1,new)
if( target in words):
dfs(begin,0,v)
return answer
Author And Source
이 문제에 관하여([Python3]프로그래머스_단어변환), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beanzinu/Python3프로그래머스단어변환저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)