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

Soorim Yoon·2022년 9월 27일
0
post-custom-banner

문제

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

실행 결과

참고

https://velog.io/@op032/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8B%A8%EC%96%B4-%EB%B3%80%ED%99%98python

profile
👩🏻‍💻 AI를 좋아하는 IT학부생
post-custom-banner

0개의 댓글