[프로그래머스] Level3 | 단어 변환 | dfs/bfs

1. 문제 설명 & 제한 사항

 

2. 나의 풀이

from collections import deque

def solution(begin, target, words):
    if not target in words:
        return 0
    
    queue = deque([(begin,0)])
    ls = [[w for w in word] for word in words]
    visited = [False for _ in range(len(words))]
    answer = 0
    
    while queue:
        current, answer = queue.popleft()

        if current == target:
            return answer
        
        idx = 0
        for l in ls:
            if not visited[idx]:
                cnt = 0
                for i in range(len(l)):
                    if l[i] != current[i]:
                        cnt += 1
                if cnt == 1:
                    answer += 1
                    queue.append((''.join(l), answer))
                    visited[idx] = True
            idx += 1
    return

 

3. 나의 아이디어

최단경로를 구하는 거니까 bfs

hit hot 될라면 가운데 글자만 이동해야하고
hot dot 될라면 첫번째 글자만 이동해야하고
dot dog 될라면 마지막 글자만 이동해야하고

하나만 다른 녀석을 골라야하고
visited하지 않았던 애를 골라야하고

hit -> hot 1
hot -> dot2 lot 2
dot -> lot3 dog 3
lot -> dog log 4
dog -> log cog 4
log -> cog

• target이 애초에 words에 들어있지 않으면 꽝이니까 먼저 처리해주는 if문 구현 -> return 0
• begin을 queue에 넣으면서 단어 변환 횟수 answer를 같이 넣어줌
• words에서 각각의 단어를 글자 하나씩을 원소로 갖도록 이중 리스트로 변환
• 방문을 기록할 visited를 단어별로 처리할 수 있도록 단어 개수로 맞춰줌
• queue가 빌 때까지 while문 돌기. 물론 그 전에 return되어서 실제로 return None값은 없을 것으로 예상
• queue의 첫번째 원소를 뽑는다. 여기서 원소는 (current, answer)로 뽑힐 것이므로 각각 받아줌
  그리고 여기서 current는 글자가 아닌 단어 형태
• current와 target이 같을 때, 그니까 current가 결국 target까지 도달한, 마지막에는 answer을 바로 return하도록
• 이중 리스트 ls에서 하나의 리스트씩 접근하도록 for문 구성
  이렇게 하면 내가 지금 접근한 원소의 위치, index를 알 수 없으므로 idx를 하나씩 늘려주려고 함
  근데 쓰면서 생각해낸게.... 그냥 for문에서 ls 가져올때 enumerate로 돌았으면 됐음;;
• 지금 접근한 단어에 방문한 적 없었던 경우에만 if 문 돌도록
• 단어 속의 글자가 몇개 다른지 확인하는 for문 작성
  몇개 다른지는 cnt로 셀건데, 글자마다 접근해서 확인
• cnt가 1인 경우, 그니까 딱 한 글자만 다른 단어의 경우에 대해서 단어 변환 횟수 answer를 하나 키워주고
  queue에 해당 단어를 추가해줄건데, 나는 글자가 아닌 단어로 추가해줘야하므로 join해줘야함
  그리고 처음 queue 구성할 때처럼 튜플로 (단어, answer) 형식으로 append
• 단어 queue에 넣었으니 visited는 True로 바꿔주고
• 다음 단어의 인덱스 접근할 수 있도록 idx 키워주고
  enumerate로 했으면 이거 필요 없었을텐데..

 

4. 기억해야할 개념

• 처음 queue를 구성할때는 시작하는 값과 동시에 return할 값을 같이 넣어주는게 포인트
  그리고 리스트로 같은 위치의 원소로 append하기보다는 튜플로 묶어서 같이 불러올 수 있도록 하자!
• 인덱스, 원소 각각 접근 해야할때는 enumerate 떠올리기. 원래 잘했는데 흠... 왜 잊어먹었지
• visited 처리해주는 위치 다시 한번 생각하고 쓰기 - 매번 헷갈려하는 것 같음
• 사실상 나는 지금 단어의 글자 하나씩 접근하는걸 직관적으로 하고자 이렇게 되었는데
  마지막엔 또 join해야하는 상황이 발생
  다른 사람의 코드 보면 애초에 for문을 단어가 아닌 index로 돌고, 글자 비교할 때는 이중 리스트 index로 접근
  이렇게 구성하면 queue에 append할때도 join할 필요 없음

for i in range(len(words)):
    temp_cnt = 0
    if not V[i]:
    	for j in range(len(word)):
            if word[j] != words[i][j]:
                temp_cnt += 1
        if temp_cnt == 1:
            q.append([words[i], cnt+1])
            V[i] = 1