난이도

LEVEL 3

문제

문제 바로가기

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

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

문제 검토

결국 target까지 도달하기 위한 최단경로를 구하는 문제이다.
BFS를 떠올릴 수 있다.

예제를 아래와 같이 노드로 표시해서 depth를 구상해보면

매 반복때마다 BFS로 탐색하여 cog까지 도달하게 되면 4단계의 depth를 가진 경로를 찾을 수 있다.

풀이(python)

Python

from collections import deque

#한 글자만 다른지 체킹
def checking(x,y):
    cnt=0
    for i in range(len(x)):
        if x[i]!=y[i]:
            cnt+=1
    if cnt==1:
        return True
    return False
    
def BFS(begin,target,words):            
    q=deque()
    check=False
    #시작 단어와 시작 depth를 큐에 append(tuple)
    q.append((begin,0))
    #words에 target이 있는지 체킹
    for x in words:
        if x == target:
            check=True
    if not check:
        return 0
    
    while q:
        cur,depth=q.popleft()
        if cur==target:
            return depth
        #계속해서 넓은 범위로 탐색 수행, 그에 대한 깊이도 카운트
        for x in words:
            if checking(cur,x):
                q.append((x,depth+1))
                        
def solution(begin, target, words):

    return BFS(begin,target,words)

일단 변환가능한지 check하고 가능하다면 큐에 append해서 다음 depth에서 BFS탐색을 시작한다.
그리고 마지막으로 target에 도달하게 되었을 때 depth를 리턴한다.

Python - 방문 확인 코드

from collections import deque

#한 글자만 다른지 체킹
def checking(x,y):
    cnt=0
    for i in range(len(x)):
        if x[i]!=y[i]:
            cnt+=1
    if cnt==1:
        return True
    return False
    
def BFS(begin,target,words,visited):            
    q=deque()
    check=False    
    #words에 target이 있는지 체킹
    for x in words:
        if x == target:
            check=True
    if not check:
        return 0
    for x in range(len(words)):
        if checking(begin,words[x]):
            q.append((words[x]))
            if not visited[x]:
                visited[x]+=1
    while q:
        cur=q.popleft()
        idx=words.index(cur)
        if cur==target:
            return visited[idx]
        #계속해서 넓은 범위로 탐색 수행, 그에 대한 깊이도 카운트
        for x in range(len(words)):
            if checking(cur,words[x]):
                q.append((words[x]))
                if not visited[x]:
                    visited[x]=visited[idx]+1
                        
def solution(begin, target, words):
    visited = [0 for _ in range(len(words))]
    return BFS(begin,target,words,visited)

백준 1697 숨바꼭질
앞선 풀이처럼 depth로 풀고 며칠 후 위 백준 문제를 depth를 사용한 풀이로 풀다가 메모리 초과와 시간 초과로 풀지 못한 경우가 생겼다.
결국 방문처리 기법을 사용한 BFS로 문제를 풀었다.

문제를 푼 후 다시 이 '단어 변환' 문제가 생각났다.
이 문제는 n의 범위가 작았기 때문에 단지 depth로 풀 수 있었던 것 같다.

그럼 이 문제의 범위가 엄청나게 커진다고 가정했을 때 방문처리 기법을 사용한 BFS로 문제를 풀어봐야겠다고 생각했다.

첫 문자는 words에 들어가 있지 않기 때문에 따로 처리를 해주고 그 다음부터 큐의 유무로 무한 반복을 해준다.

words안에서 현재 단어의 index를 찾고 visited와 매핑하여 방문처리를 하였다.

걸린 시간

45분 37초

총평

레벨 3의 문제였지만, BFS를 적용해서 푸니 레벨 2의 구현 문제보다 간단하게 느껴졌다.
더 많은 알고리즘을 익히는 것이 중요하다고 느끼게 되는 문제이다.