프로그래머스 단어 변환

BFS, DFS 두가지 방법으로 다 풀 수 있는 것 같다.

DFS로 target에 도달할 때까지의 모든 거리 중 최소 거리를 구하면 될 것 같았는데 막상 해보니까 잘 안됐다..

BFS로 풀었다. 레벨별로 그래프 탐색을 하다가 target을 만나면 도달하는데 걸린 거리를 반환하면 된다.

 

시작하는 노드를 queue에 넣고 while문을 돌린다.

while문이 끝날 때까지 answer를 찾지 못하면 0을 반환한다.

checker는 BFS를 하면서 이전 레벨의 노드를 재방문하지 못하게 하기 위한 것이다.

queue_tmp를 생각해내기 어려웠는데, queue만 사용해서 노드를 추가하게 되면 레벨이 증가할 때마다 answer가 증가하는 게 아니라 같은 레벨의 노드를 방문하는데도 answer를 증가시키게 된다.

queue_tmp를 이용해서 다음에 방문할 자식 노드들을 한번에 넣어뒀다가 answer를 1만 증가시키고 자식들을 다 방문해야 한다.

def solution(begin, target, words):
    queue = [begin]  # root부터 시작
    checker = [False] * len(words)  # 방문 확인
    answer = 0
    while queue:
        queue_tmp = []  # 같은 level에 있는 node 저장
        current = queue[0]
        queue.remove(current)
        answer += 1  # 다음 레벨로 이동하면서 1 증가
        for i, word in enumerate(words):  # current와 비교해서 문자 1개만 다른 노드 찾기
            if not checker[i]:  # 방문하지 않은 노드라면
                count = 0
                for x, y in zip(current, word):  # 현재 방문한 노드와 words에 있는 노드 비교
                    if x != y:
                        count += 1
                if count == 1:  # 문자 1개만 다르고
                    if target == word:  # target이면 answer 반환 후 종료
                        return answer
                    checker[i] = True  # 조건에 맞는 자식이면 방문 표시
                    queue_tmp.append(word)  # 같은 레벨에 있는 노드들 삽입
        queue = queue_tmp[:]  # 다음에 탐색할 node들 queue에 전달
    return 0  # 탐색이 완전히 끝나고 target을 찾지 못하면 0

print(solution('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']))  # 4
print(solution('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log']))  # 0
print(solution('hit', 'hhh', ['hhh', 'hht']))  # 2
print(solution('hit', 'zzz', ['aaa']))  # 0
print(solution('hit', 'zzz', ['zzz', 'zyz', 'xzz', 'xyz', 'hyt', 'hyz', 'xiz', 'hiz']))  # 4

 

근데 테스트 케이스가 이런 경우는 노드가 끊겨서 bfs가 안된다...

 

print(solution('aaa', 'abc', ['aaz', 'aab', 'abb', 'abc']))

 

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