단어 변환(★★★ / ▲▲ / 2) - Python / Javascript

기운찬곰·2020년 12월 15일

DFS/BFS 프로그래머스

프로그래머스

목록 보기

2/9

개요

풀이 시간 : 30분
시간 제한 : -
메모리 제한 : -
기출 : 프로그래머스 연습문제
링크 : https://programmers.co.kr/learn/courses/30/lessons/43163

문제

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

한 번에 한 개의 알파벳만 바꿀 수 있습니다.
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 합니다.

입출력예

해결방법

전형적인 DFS/BFS 문제이다(정확히 말하면 BFS 문제다). 왜냐면 hit부터 시작해서 한번에 한개의 알파벳만 바꿀 수 있는 단어를 단어집합에서 찾고, 그 찾은거에서 또 찾고 찾고... 반복하면 되기 때문이다.

주의할 점

기존에 방문했던거는 넣으면 안된다. BFS를 사용하면 굳이 다시 방문해서 계산할 필요가 없기 때문이다. 난 처음에 방문을 그래도 해야 하지 않나 싶었는데 하지마라.. ㅡ.ㅡ
begin이란 단어도 words에 포함되어있을 수 있다. 따라서 words에 begin을 제거하던가 다시 방문하지 않도록 조치를 해야 한다.
한 번에 한 개의 알파벳만 바꿀 수 있다. 로직이 제대로 구현되었는지 다시 살펴보자.

Python

내 코드

from collections import deque

def one_diff(w1, w2):
    if w1 == w2:
        return False

    cnt = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            cnt += 1
            if cnt > 1:
                return False

    return True


def solution(begin, target, words):
    ## BFS로 구현
    ## (word, dist) 형태로 초기화
    words_dist = []
    for w in words:
        words_dist.append([w, -1])

    q = deque([(begin, 0)])

    while q:
        print(q)
        cur_word, cur_dist = q.popleft()

        if cur_word == target:
            return cur_dist

        for i in range(len(words_dist)):
            # 방문하지 않았고 1개 차이가 나는경우에만 업데이트하고 큐에 추가
            if words_dist[i][1] == -1 and one_diff(cur_word, words_dist[i][0]):
                words_dist[i][1] = cur_dist + 1
                q.append((words_dist[i][0], words_dist[i][1]))

    return 0


print(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))

one_diff 함수를 처음에 잘못만들어서 시간이 오래걸렸다..🤦‍♂️🤦‍♂️ 문제가 뭐냐면 알파벳을 한번에 한개의 알파벳만 바꿀 수 있다고 했다. 따라서 hih를 hhi로 바꾸는경우는 2번 바꾸는 것이므로 첫번째 함수는 잘못 만들었다고 볼 수 있다.

두번째 만든 함수처럼 순서를 맞춰서 비교해야 한다.

Javascript

내 코드

const bfs = (start, target, words) => {
  const queue = [[start, 0]];
  
  // ✅ words에 있던 begin이 있다면 제거
  if (words.indexOf(start) > -1) {
    words.splice(words.indexOf(start), 1);
  }

  while (queue.length > 0) {
    const [cur, dist] = queue.shift();

    if (cur === target) return dist;

    // 한글자 차이나는 단어들 찾음
    const possible = words.filter((word, idx) => {
      if (word.length !== cur.length) return true;

      let cnt = 0;
      for (let i = 0; i < word.length; i++) {
        if (word[i] !== cur[i]) {
          cnt += 1;
          if (cnt > 1) return false;
        }
      }
      words.splice(idx, 1);
      return true;
    });

    // 찾아서 큐에다가 넣어줌
    possible.forEach((word) => {
      queue.push([word, dist + 1]);
    });
  }
};

function solution(begin, target, words) {
  // BFS 문제
  const result = bfs(begin, target, words);
  return result ? result : 0;
}

console.log(solution('hot', 'lot', ['dot', 'dog', 'lot', 'log']));

words에 있던 begin을 제거하는 코드에서 실수를 해서 조금 시간이 걸렸다. 나는 처음에 이 부분을 아래처럼 구현했었다. 이는 미처 words에 begin이 없는 경우를 고려하지 않은 경우이다.

words.splice(words.indexOf(start), 1);

String.prototype.indexOf(searchValue) : 호출한 String 객체에서 주어진 값과 일치하는 첫 번째 인덱스를 반환해주며, 일치하는 값이 없으면 -1을 반환한다.
Array.prototype.splice(start[, deleteCount]) : 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경해준다. 주로 쓰이는 곳은 기존 요소 삭제할 때이다. start에는 배열의 변경을 시작할 인덱스를 넣어주며 음수인 경우 배열의 끝에서부터 요소를 세어간다. (원점은 -1을 의미)

따라서 word에 begin이 없는 경우 indexOf에서 -1을 반환하며 splice에서는 start에 -1을 넣어주면 원점을 의미하므로 어처구니 없게 첫번째 요소가 그냥 날아가버리는 문제가 생기게 된다.