💬

단어 변환

레벨

LV.3

날짜

Oct 4, 2023

링크

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

🔎 문제

school.programmers.co.kr

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

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

BFS, 큐

시행착오

word를 하나씩 꺼내 비교 → 배열 형태로 저장 [word, count]

코드

정은

구현

파이썬으로 bfs를 구현했다.

전체적인 구현 방법은 어제 한 게임 맵 최단거리와 흡사하다.

자세한건 코드에..

코드

종혁

구현

시작단어에서 한글자가 다른 단어를 찾아서 이동 - 그 다음 글자에서 또 한글자 찾아서 이동 … - target 단어로 이동하면 지금까지 이동했던 횟수를 return

compareWords 함수를 이용해서 단어들을 한 글자씩 비교

이동횟수 중 가장 작은 값이 답이 됨

코드

재웅

구현

'최소' 몇 단계의 과정인지? -> 최단거리 -> BFS(Queue)

계속 Queue에 집어넣을건데, 방문처리를 해줘야 할 듯 함

파생되는 함수마다, 있는지 없는지 여부만 판단하면 되기 때문에 Set으로

방문하지 않은 원소 중, 하나만 바꿔서 만들 수 있는 문자를 찾아 -> change 함수

코드

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

배운 점

큐는 집어넣을 때 방문처리!
배열 형태로 큐에 넣는 법

👧🏻

정은

범위가 작아서 pop(0)이 잘 먹혔던 것 같기도.. 범위가 큰 문제도 다음번에 풀어봐야겠다

라이브러리 deque의 popleft() 시간복잡도 = O(1)

찾아보니 코테에서 표준라이브러리는 허용 되는 것 같아서, 써도 괜찮을 것 같다.

👦🏻

종혁

글자 비교 함수를 좀더 빠르게 하는 방법을 찾으면 좋을것 같다

👦🏻

재웅

shift()를 쓰지 않는 방향으로도 리팩토링해봐야겠다..


function solution(begin, target, words) {
    let answer = 0;
    const queue = [];
    const visited = new Array(words.length).fill(false);
    
    // words에 target이 있는지 확인
    if(!words.includes(target)) { return; }
    
    // 큐에 begin, answer 배열 형태로 넣기
    queue.push([begin, answer]);
    
    while(queue) {
        let [value, count] = queue.shift();
        if(value === target) {
            return count;
        }
        
        words.forEach((word, index) => {
            if(visited[index]) return;
						// 다른 개수 체크
            let notEqual = 0;
						for(let i = 0; i < word.length; i++) {
                if(word[i] !== value[i]) notEqual++;
            }
            
            if(notEqual === 1) {
                queue.push([word, ++count]);
                // 큐는 집어 넣을 때 방문처리
                visited[index] = true;
            }
        });
    }
    return answer;
}


def solution(begin, target, words):
    answer = 0
    
    if target not in words: #배열에 없으면 애초에 못만들기 때문에 굳이 연산할 필요가 없다
        return 0;
    
    queue = [begin] #bfs, 큐
    
    while queue:
        queue_size = len(queue)

        for _ in range(queue_size): #1턴은 시작했을 때 큐 사이즈 만큼만
            current = queue.pop(0)

            if current == target: #현재가 target이면 bfs 종료
                return answer

            for word in words: #단어 철자 맞춰보기
                diff = 0

                for w,c in zip(word,current):
                    if w != c: #단어끼리 차이를 세어본다
                        diff+=1

                if diff == 1:
                    queue.append(word)

        answer+=1 #시작문자에서 철자 하나를 바꾼 횟수
    
    return 0


function solution(begin, target, words) {
    //시작 글자에서 한글자로 바꿀 수 있는것들을 찾아서 - 계속 가다가 다하면 끝나는거
    if(!words.filter((v) => v === target).length){return 0}
    const compareWords = (first,second) => {
        let diff = 0
        for(let i=0;i<first.length;i++){
            if(diff >= 2){break}
            first[i] !== second[i] && diff ++ 
        }
        return diff === 1 ? second : false 
    }
    const result = []
    const dfs = (startWord,isUsed,sum) => {
        if(startWord === target){
            result.push(sum)
            return}
        for(let i=0;i<words.length;i++){
            if(isUsed[i]){continue}
            //word랑 words[i]랑 한글자 빼고 다 같은지 비교
            const nextWord = compareWords(startWord,words[i])
            if(!nextWord){continue}
            else{
                isUsed[i] = 1
                dfs(nextWord,[...isUsed],sum+1)
                isUsed[i] = 0
            }
        }
    }
    dfs(begin,Array(words.length).fill(0),0)
    return Math.min(...result)
}


function solution(begin, target, words) {
    const visited = new Set();
    visited.add(begin);
    
    // 큐 초기화 (시작단어, 카운트, 방문여부)
    const queue = [[begin,0,visited]];

    while (queue.length !==0) {
        const [currentWord, count, visited] = queue.shift();
        if (currentWord === target) return count;
        
        for (let i = 0; i < words.length; i++) {
            const nextWord = words[i];
            if (!visited.has(nextWord) && change(currentWord, nextWord)) {
                visited.add(nextWord);
                queue.push([nextWord, count + 1,visited]);
            }
        }
    }
    return 0;
}

// 지금 단어와 현재 단어가 한 글자 바꿔 변환이 가능하다면 True, 아니면 False 반환
function change(currentWord, nextWord){
    const length = currentWord.length
    let differCount = 0
    
    for(let i=0;i<length;i++){
        if(currentWord[i]!==nextWord[i]) differCount++
        if(differCount>1) return false
    }
    return true
}