Py) 프로그래머스 43163 단어 변환

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

코딩테스트 연습 - 단어 변환

from collections import deque


def bfs(begin, target, words, visited):
    if target not in words:
        return 0

    deq = deque([[begin, 0]])  # 주의

    while deq:
        cur, depth = deq.popleft()

        if cur == target:
            return depth

        for i in range(len(words)):
            if visited[i] == True: continue
            cnt = 0
            for a, b in zip(cur, words[i]):
                if a != b:
                    cnt += 1
            if cnt == 1:
                visited[i] = True
                deq.append([words[i], depth + 1])  # 주의


def solution(begin, target, words):
    answer = 0
    visited = [False] * len(words)
    answer = bfs(begin, target, words, visited)

    return answer

 

문제 풀기에 앞서서 BFS, DFS 판단 기준을 좀 찾아봤다.

이 문제는 방문 여부 확인이 필요하고, 규모가 크지 않으니까 BFS를 사용했다.

 

* 기본 아이디어

글자 하나하나 비교해 하나만 다른 것을 큐에 넣는다 (depth로 표시)

words 내의 단어 순서에 따라 달라지지 않을까 싶었는데 중간에 target과 일치하는지 확인하는 소스를 넣음으로써 이와 같은 일 방지.

 

* 피드백

치명적인 실수를 했는데 거기서 시간을 굉장히 많이 까먹었다. 

처음에 deq 선언을 이렇게 함

deq = deque([begin, 0])

1차원 리스트인거임

근데 이래 놓고 

cur, depth = deq.popleft()

여기서 에러나니까 ???? 하고 한참 헤매었음

저건 뭐 popleft를 두 번하면 되니까 해결 한다면 할 수 있었지만 그 다음에서 문제가 발생했다.

if cnt == 1:
    visited[i] = True
    deq.append([words[i], depth + 1])

이렇게 append 해버린 것이었다.. 그러니까 위에서는 1차원 리스트고 밑에서는 2차원 리스트로 넣어버린 것이다...

당연히 루프를 돌면서 popleft()를 두번 한 곳에서 에러가 발생했고 또 어리둥절했음.

발견 못해서 디버깅해야겠다 싶어서 뒤늦게 파이참 깔고 디버깅 돌림,,

발견해서 정신 차리고 deq을 2차원 리스트로 고쳤다.

deq = deque([[begin, 0]])  # 고침

while deq:
    cur, depth = deq.popleft()

popleft도 처음 바라던 데로 한 번에 해버릴 수 있었고.

결론: deq 선언할 때 리스트 차원 조심할 것

 

*

zip() 여러 개의 순회 가능한 객체를 인자로 받고 각 객체가 담고 있는 원소를 튜플의 형태로 차례로 접근할 수 있는 반복자를 반환함.

- 병렬 처리: 2개 이상의 인재를 넘겨받으면 해당 문자열 내의 글자를 한 글자씩 병렬한다.  -> 이번 문제에서 아주 잘 씀

- unzip: 리스트 앞에 * 연산자를 붙인다.

- 사전 변환: key, value로 이루어진 상태로 dict()에 넘기면 사전 형태로 변환됨

- zip에 넘겨주는 인자의 길이가 다를 때(길이가 다른 list): 가장 짧은 인자를 기준으로 데이터가 엮임

https://www.daleseo.com/python-zip/