Sol 1 : DFS(초기코드)
answer = 51
def solution(begin, target, words):
global answer
visited = [begin]
cnt = dfs(begin, target, words, visited, 0)
print("cnt :", cnt)
if answer == 51:
return 0
return cnt
def dfs(begin, target, words, visited, k):
global answer
# 종료 조건(begin == target)
if begin == target :
print("FIN :",k)
answer = min(answer, k)
print("answer :", answer)
return answer
for i in range(len(begin)):
# i번째 알파벳 제외하고 비교
barr = list(begin)
barr.pop(i)
for word in words:
warr = list(word)
warr.pop(i)
# i번째 빼고 다 같으면 변환 가능
# bfs 이어감
if (barr == warr) and (word not in visited):
# print("barr :", barr, "warr :", warr)
# print("Changed : ", word, k)
visited.append(word)
dfs(word, target, words, visited, k + 1)
visited.pop()
# 변환 못하면 0
return answer
두 단어가 한 글자만 다른지 판단하는 로직
-
(기존) 두 단어를 리스트로 split()하여 for 문으로 i번째 인덱스 요소를 pop하고 리스트가 같은지 판단 -> pop(i)연산, 비교 연산, 리스트 연산이 일어나 비효율적
-
(변경) for 문으로 동시에 i번째 문자를 비교하고, 다른 개수를 count하여 비교 + count가 2가 넘어가면 바로 return 처리해서 끊어주기 + zip() 함수 사용해도 됨
visited 리스트
-
(기존) : visited 리스트를 dfs 함수 인자로 전달하고, append()/pop()을 통해 상태 관리 -> not in visited 체크는 O(n)의 시간 복잡도를 가짐
-
(변경) : set() 자료구조를 이용하면 O(1)의 시간 복잡도를 가짐
초기 answer 설정
- 최솟값을 찾는 경우 INF로 설정하는 것이 좋음 -> answer = float("inf") or float("-inf")
Sol 2 : DFS(최적화)
answer = float('INF')
def solution(begin, target, words):
visited = {begin} # begin 담은 visited set
# dfs : 시작단어, 목표 단어, 단어 배열, visited 배열, 변환 횟수
dfs(begin, target, words, visited, 0)
# 변환 실패하면 0 return
if answer == float('INF'):
return 0
else :
return answer
def dfs(begin, target, words, visited, k):
global answer
# 종료 조건(begin == target)
if begin == target :
answer = min(answer, k)
return
# 단어 목록 돌면서 변환 가능한 단어 탐색
for word in words:
# 아직 방문 안했으면
if word not in visited:
# 변환 가능한지 체크
diff_cnt = 0
for b, w in zip(begin, word):
if b != w : diff_cnt += 1
if diff_cnt > 1 : break # 다른 알파벳이 1개가 아니면 그냥 바로 탈출
# 변환 가능하면(다른 알파벳이 1개)
if diff_cnt == 1:
visited.add(word) # 방문 표시
dfs(word, target, words, visited, k+1)
visited.remove(word) # 다른 경로에서도 방문할 수 있도록 remove
