[DFS, BFS] 단어변환 (프로그래머스, Level 3)

Soorim Yoon·2022년 9월 27일

BFS DFS 코테 프로그래머스

알고리즘 & 코딩테스트

목록 보기

31/67

문제

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

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해라.
begin은 처음 주어진 시작 단어이며, target은 begin이 최종적으로 도달해야 하는 정답 단어이다.

풀이

BFS 알고리즘을 사용해 본 문제를 구현하였다. 코드 구현 단계는 다음과 같다.

queue를 선언하고 visited 배열을 생성한다.
큐에 [begin, count] 쌍을 삽입한다. begin은 처음 시작하는 단어이고 count는 현재까지 단어를 변환한 횟수이다.
큐에 삽입된 단어를 pop해서 현재 단어, 현재 변환 횟수로 nword, ncnt 변수에 대입한다.
현재 단어가 target 값과 같으면 현재 변환 횟수인 ncnt를 정답으로 리턴한다.
단어가 다르다면 words 배열의 모든 단어들을 순차적으로 탐색하며, visited 여부가 0(False)인 단어를 대상으로 현재 단어와 몇 글자가 다른지 확인한다. 이 때 다른 글자의 개수는 tmp_cnt 변수에 저장한다.
tmp_cnt 변수 값이 1인 경우 (= 한 글자만 다른 경우) 해당 단어와 ncnt에 1을 더한 값을 큐에 삽입한다. 이때 해당 단어의 vistied 여부도 1(True)로 바꿔준다.

코드

💡 정답 코드 (최종)

BFS를 알고리즘을 활용해 구현했다.

from collections import deque

def solution(begin, target, words):
    answer = 0
    visited = [0 for i in range(len(words))]       # 단어의 개수만큼 visited 배열 생성
    
    queue = deque()
    queue.append([begin, 0])    # 시작 단어, 단어변환 횟수를 큐에 삽입

    while queue:
        nword, ncnt = queue.popleft()
        
        if nword == target:     # 현재 단어가 target 단어와 같다면 현재까지의 변환 횟수를 리턴
            answer = ncnt
            break
        else:   # 다르면, 한 글자만 다른 단어를 찾아야 함
            for i in range(len(words)):     # words 배열의 모든 단어들의 visited를 탐색
                if visited[i] == 0:     # 방문하지 않은 노드이면 해당 단어가 현재 단어와 몇 글자가 다른지 파악
                    tmp_cnt = 0
                    for j in range(len(nword)):
                        if nword[j] != words[i][j]:
                            tmp_cnt += 1    # 글자가 다른 자리마다 temp count 값을 1씩 추가
                    if tmp_cnt == 1:    # 한 글자 다른 단어이면
                        ncnt += 1   # 변환 횟수를 증가시킴
                        queue.append([words[i], ncnt])   # 바꿀 단어를 큐에 삽입
                        visited[i] = 1      # 방문 여부를 참으로 바꿈

    return answer

실행 결과

시간 초과 코드

def solution(begin, target, words):    
    if target not in words:     # target 단어가 words 배열에 없으면 0을 리턴
        return 0
    
    answer = 0
    while(1):
        arr = [0 for _ in range(len(words))]    # words 배열과 같은 길이의 배열을 생성해서 현재 begin과 배열 안 각 단어들의 글자 수 차이를 기록함
        for s in range(len(words)):
            val = 0
            for i in range(len(words[s])):
                if begin[i] != words[s][i]:
                    val += 1
            arr[s] = val

        for i in range(len(arr)):   # arr 배열에 기록한 숫자를 통해 한 자리만 다른 단어를 begin 값으로 교체
            if arr[i] == 1:
                begin = words[i]
        answer += 1     # 교체할 때마다 교체 횟수를 1씩 증가시킴
        
        if target == begin:
            return answer

실행 결과

오답 코드

# 오류 발생 코드 (테스트 케이스의 값과 틀림)

def solution(begin, target, words):    
    if target not in words:     # target 단어가 words 배열에 없으면 0을 리턴
        return 0
    
    answer = 0
    while target != begin:      # target 값에 도달하지 못한 경우 while문 반복 
        for s in words:        
            d = 0
            for i in range(len(s)):
                if begin[i] != s[i]:      # begin과 s 단어의 각 자리가 같은지 비교
                    d += 1      # 다르면 변수에 1을 더해 기록
            
            change = 0
            if d == 1:      # 한 자리만 다른 단어이면
                begin = s       # 단어를 바꿔줌
                change += 1     # 단어를 바꾸는 경우를 기록
            else:
                continue
            
            if change == 1:
                answer += 1

        return answer