Coding test(Python3)/Programmers

[level 3] 단어 변환(+dfs, bfs 정리)

녜잉 2024. 7. 4. 16:32

1. 문제

두 개의 단어 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 합니다.

 

2. 문제 풀이 

1) target 단어가 words 배열에 없다면 0을 반환한다. 

2) 큐와 visited을 각각 초기화한다.  이때, 큐의 경우 count를 함께 저장해야 하므로 set()을 사용한다.

3) 큐에 원소가 있는 동안 반복문을 진행한다. 

4) popleft()함수를 사용하여, 현재 왼쪽에 있는(가장 첫번째) 단어와 count를 꺼내어 각각 current와 count로 선언한다.

5) 만약 current(현재 단어)와 target이 같은 단어라면 count(변환 횟수)를 반환한다. 

6) words의 원소를 사용하여 for문을 진행한다. 

만약, word를 방문한 적이 없고, check_one함수의 값이 True라면 해당 단어를 visited에 넣고(방문 했음을 체크)  큐에 해당 단어와 count+1을 넣는다. 

  • check_one 함수에서는 현재 단어와, 다른 단어의 글자가 한글자씩만 다른지를 확인한다.
  • a와 b가 다를 때마다 1을 더하고, 해당 값이 1인지를 확인하여 맞다면 true, 아니라면 false를 반환한다. 

7) 큐가 비었음에도 도달하지 못한 경우는 바꾸지 못하는 경우이므로 0을 반환한다. 

from collections import deque

def check_one(word1, word2):
    
    diff_count = sum(1 for a, b in zip(word1, word2) if a != b)
    
    return diff_count == 1 #diff_count가 1인지 아닌지 여부 반환 

def solution(begin, target, words):
    if target not in words:
        return 0
    
    queue = deque([(begin, 0)])
    visited = set()
    
    while queue:
        
        current, count = queue.popleft()
        
        if current == target:
            return count
        
        for word in words:
            if word not in visited and check_one(current, word):
                visited.add(word)
                queue.append((word, count+1))
                
    return 0

 

 

 

dfs랑 bfs 문제를 풀다보니까 visited을 선언함에 있어서 두 문제에 차이점이 있는 것이 보였다. 

 

bfs에서는 visited 체크 여부를 위해 set 자료형을 사용하는 반면, dfs에서는 리스트 형을 주로 사용하는 것 같아, 해당 부분을 챗gpt에게 물어보았다...ㅎ 

 

BFS

  • bfs(너비 우선 탐색)은 그래프에서 최단 경로를 찾기 위해 자주 사용
  • 시작점에서부터 모든 인접 노드를 먼저 탐색한 후, 그 다음 인접 노드를 탐색하는 식으로 진행
    • 따라서, 특정 노드에 도달 했을 때, 해당 노드로 가는 경로가 항상 최단 경로가 됨 
  • 각 노드를 한 번만 방문 해야 하므로, 방문한 노드를 빠르게 확인하고 재방문 방지를 위해 해시셋을 사용
    • 해시셋은 평균적으로 O(1) 시간 복잡도로 삽입 및 조회 가능 

 

DFS

  • 그래프를 한 경로를 따라 끝까지 탐색한 후, 다른 경로로 돌아가면서 탐색 진행 
  • 모든 경로를 탐색하거나, 특정  조건을 만족하는 경로를 찾을 때 유용
  • 탐색 특성상, 재귀나 스택을 사용하여 구현
    • 리스트는 인덱스를 통해 방문 여부를 쉽게 체크 가능, 자주 사용됨 

 

BFS는 최단 경로를 찾을 때 자주 사용되며 인접한 노드를 탐색하고, 그 다음 노드를 탐색

DFS는 모든 경로를 찾거나, 특정 조건을 만족하는 경로를 찾을 때 사용. 한 경로를 따라서 끝까지 탐색 후, 다른 경로를 돌아가며 탐색 

 

문제 여러 개 푸니까 확실히 DFS랑 BFS 차이점은 이제 알겠다 물론 아직 바로 문제 푸는 거는 못하지만..

플그 문제 풀면서 개념 익히고 백준에서 문제집으로 더 풀어봐야지...ㅎ