[프로그래머스] 파이썬 _ 단어변환 ⭕️

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

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

문제유형 : DFS/BFS

 

문제풀이

 

DFS의 경로상에 순서가 있는경우 (a-b-c 와 a-c-b가 다른경우!!) dfs의 재귀호출이 리턴되는 지점에서 방문처리를 다시 풀어줘야한다

 

• 단어가 하나의 노드가되고 차이가 1인 노드끼리 연결되있다고 생각한다.
• 현재노드로부터 차이가 1인 노드들을 순차적으로 방문탐색하면서 target을 찾아간다.
• DFS로 풀때 내가 푼 방식 : 차이가 1인 노드를 찾을때, 이미 방문했던 노드는 다시 방문하면 안되므로 이를 처리해주다가 dfs의 재귀가 끝나는 지점에서 차례로 다시 방문을 풀어주어야한다
• BFS로 풀때 내가 푼 방식 : 같은 리프선상에 있는 노드를 큐에 넣는데, 이때 그다음 depth로 넘어갈때 큐에있는걸 하나씩 빼주는게 아니라 전체를 다 빼도록 하여 한번의 루프당 하나의 depth로 넘어갈수 있도록 해야한다. 

 

• 이 문제는 DFS/BFS 둘다 가능하지만 BFS가 더 좋은 풀이라고 생각한다.
  •  bfs는 같은 리프노드들 순차적으로 탐색하는 방식이여서 bfs로 찾은 해는 최단거리의 해라는걸 바로 증명할 수 있는 반면 dfs로 해를 찾으면 모두 탐색을 해본 뒤 최적의 해를 찾아야하기 때문

정답코드1 ( DFS로 풀이)

import sys
sys.setrecursionlimit(10 ** 6)

visited = []
result = []

def solution(begin, target, words):
    answer = 0

    for _ in range(len(words)):
        visited.append(0)

    if target not in words:
        return answer  # if문 안에서 리턴을 하는경우 else를 쓰지 않아도 됨

    def dfs(word, depth):
        if word == target:
            result.append(depth)
            return

        for i in range(len(words)):
            #이미 방문한 노드는 처리하지 않는다.
            if visited[i] == 1:
                continue

            #현재노드와 방문처리되지 않은 노드중 차이가 1인것
            if checkDiff(word, words[i]) == 1:
                visited[i] =1
                dfs(words[i], depth+1)
                visited[i] = 0 #이부분..! dfs가 끝나면 다시 방문처리를 풀어주는것

    dfs(begin, 0)

    answer = min(result)
    return answer


def checkDiff(word, target):
    diff = 0
    for i in range(len(word)):
        if word[i] != target[i]:
            diff += 1
    return diff

DFS풀이 2( 210615 다시풀어봄 - 20분걸림 )

num_list = []
def solution(begin, target, words):
    answer = 0
    if target not in words:
        return answer
    words.append(begin)

    visited = {}
    for i in words:
        visited[i] = False

    node_dic = {}

    for i in words:
        node_dic[i] = []

    for i in words:
        for j in words:
            if checkDiff(i, j) == 1:
                node_dic[i].append(j)


    dfs(begin, target, node_dic, visited, 0)
    return min(num_list)



def checkDiff(source, target):
    answer = 0
    for i in range(len(source)):
        if source[i] != target[i]:
            answer += 1

    return answer

def dfs(start, target, node_dic, visited, num):
    #방문처리
    visited[start] = True

    if start == target:
        num_list.append(num)
        return

    # 연결되어있는 = 차이가 1인 노드들에 대해서
    for i in node_dic[start]:
        # 아직 방문처리 전이면
        if visited[i] == False:
            # dfs실행
            dfs(i, target, node_dic, visited, num+1)
            #dfs가 끝낫으면
            visited[i] = False # 다시 풀어준다.

정답코드2 ( BFS로 풀이) 

from collections import deque


def solution(begin, target, words):
    global answer
    answer = 0
    
    if target not in words:
        return answer

    def bfs(begin):
        global answer
        q = deque()
        q.append(begin)

        while True:
            answer += 1
            curr = []  # 현재 depth에 있는 모든 노드를 담을 리스트 
            while q:
                curr.append(q.popleft())

            if target in curr:   # target을 찾은경우 리턴
                return

            for i in range(len(curr)):   
                for j in range(len(words)):
                    if checkDiff(curr[i], words[j]) == 1:
                        q.append(words[j])

            for i in q:   # 큐에 넣어진 노드 -> 이미 깊이가 지난 노드
                if i in words:  
                    words.remove(i) #삭제하여 다시 재방문 하지 않도록 함
    bfs(begin)
    return answer-1


def checkDiff(word, target):
    diff = 0
    for i in range(len(word)):
        if word[i] != target[i]:
            diff += 1
    return diff