문제 설명
두 개의 단어 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 합니다.
알고리즘
접근을 어떻게 해야할지 고민을 해보았다. 고민을 차근차근 나열해보면..
-
target단어가words안에 들어 있지 않으면 절대 바꿀 수 없다. 중요한 예외처리.(BFS 연산 시작하기도 전에 처리해야 효율이 좋을 것이라고 생각) -
begin 단어를 바꿀 때, words안에 있는 단어와 한 글자 빼고 나머지가 모두 같아야 바꿀 수 있다. 그래서 나는 단어를 노드라 생각하고, 이 조건을 인접한 노드인지 아닌지로 판단하는 기준으로 삼겠다고 생각했다.
생각은 간단하지만 코드가 간단하지가 않다. 내 코드가 좋은 코드라고 생각이 되지는 않지만, 그렇다고 나쁜 코드는 아니지 않을까..?
실행 시간에 크게 문제가 없는 걸 보니 괜찮은 생각이었던 듯.
아, 그리고 예외중에 target이 words에 있더라도 바꿀 수 없는 경우가 있을텐데, 이 예외는 문제에 들어가 있지 않은 것 같다. 아마 내 코드는 초기 설정한 minn 값이 변하지 않는다는 조건으로 예외처리를 할 수 있을 것 같다.
정답 코드
minn = 1000 # 문제 조건에 단어가 50개 이하니까 정답이 50이하일 것이기 때문에 절대적으로 큰 수로 초기화 해주었다.
def BFS(target,words,isvisited,adj,k,ans):
global minn
isvisited[k] = True
if target == words[k]: #찾았다!
if minn > ans:
minn = ans
for i in range(len(words)):
if adj[k][i] and not isvisited[i]: # 인접하면.
BFS(target,words,isvisited,adj,i,ans+1)
isvisited[i] = False
def solution(begin, target, words):
global minn
if target not in words: # target이 words에 없으면 변환할 수 없다.
answer = 0
return answer
words.insert(0,begin) # words에 첫번째에 begin 을 넣는다. 인접한거 판단하게.
alen = len(begin) # 단어의 길이
wlen = len(words)
adj = []
for i in range(len(words)):
adj.append([]) # 인접한지를 판단하게 해주는 이차원 배열 생성.
for i in range(wlen):
for j in range(wlen):
same = 0
for k in range(alen):
if words[i][k] != words[j][k]:
same += 1
if same > 1: # 1번 이상 일치하지 않는다 => 두 글자 이상 다르다.
adj[i].append(0)
else:
adj[i].append(1)
# 인접한 것 까지 다 완성. 이제 begin에서 시작해서 따라가서 단어가 만들어지는지만 확인하면 된다.
isvisited = [False] * wlen
BFS(target,words,isvisited,adj,0,0)
return minn이 문제는 다른 사람의 코드도 한번 봐야할 듯. BFS 함수의 인자가 5개인 것이 무엇보다 찜찜하다.
