🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- BFS, 큐
- 시행착오
- word를 하나씩 꺼내 비교 → 배열 형태로 저장 [word, count]
코드
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; }
정은
구현
- 파이썬으로 bfs를 구현했다.
- 전체적인 구현 방법은 어제 한 게임 맵 최단거리와 흡사하다.
- 자세한건 코드에..
코드
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
종혁
구현
- 시작단어에서 한글자가 다른 단어를 찾아서 이동 - 그 다음 글자에서 또 한글자 찾아서 이동 … -
target단어로 이동하면 지금까지 이동했던 횟수를return
compareWords함수를 이용해서 단어들을 한 글자씩 비교
- 이동횟수 중 가장 작은 값이 답이 됨
코드
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) }
재웅
구현
- '최소' 몇 단계의 과정인지? -> 최단거리 -> BFS(Queue)
- 계속 Queue에 집어넣을건데, 방문처리를 해줘야 할 듯 함
- 파생되는 함수마다, 있는지 없는지 여부만 판단하면 되기 때문에 Set으로
- 방문하지 않은 원소 중, 하나만 바꿔서 만들 수 있는 문자를 찾아 -> change 함수
코드
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 }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- 배운 점
- 큐는 집어넣을 때 방문처리!
- 배열 형태로 큐에 넣는 법
정은
- 범위가 작아서 pop(0)이 잘 먹혔던 것 같기도.. 범위가 큰 문제도 다음번에 풀어봐야겠다
- 라이브러리 deque의 popleft() 시간복잡도 = O(1)
- 찾아보니 코테에서 표준라이브러리는 허용 되는 것 같아서, 써도 괜찮을 것 같다.
종혁
- 글자 비교 함수를 좀더 빠르게 하는 방법을 찾으면 좋을것 같다
재웅
- shift()를 쓰지 않는 방향으로도 리팩토링해봐야겠다..