알고리즘/프로그래머스
[프로그래머스] 단어 변환 -Java
dkwjdi
2020. 12. 22. 19:06
https://programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(String begin, String target, String[] words) {
return bfs(begin, target, words);
}
private int bfs(String begin, String target, String[] words) {
boolean visited[] = new boolean[words.length];
int cnt=-1;
Queue<String> queue= new LinkedList<>();
queue.offer(begin);
while(true) {
int size=queue.size();
if(size==0) return 0;
cnt++;
for(int i=0; i<size; i++) {
String str=queue.poll();
if(str.equals(target)) return cnt; //target 과 같아진다면 끝
for(int j=0; j<words.length; j++) {
if(visited[j]) continue;
if(check(words[j],str)) {
queue.offer(words[j]);
visited[j]=true;
}
}
}
}
}
private boolean check(String word, String str) {
int len=str.length();
int cnt=0;
for(int i=0; i<len; i++) {
if(word.charAt(i)==str.charAt(i)) cnt++;
}
if(cnt==len-1) return true;
return false;
}
}
소요시간 : 30분
BFS를 돌리면서 현재 단어에서 글자하나를 바꿧을 때 바꿀 수 있는 단어를 큐에 넣었습니다.
처음에 테스트케이스 3번이 나오지 않았는데 알고보니 글자하나를 바꿧을 때 가능한 글자인지 확인하는 함수에서 오류가 있었습니다.
예를 들어 hit -> hot 으로 변환은 가능합니다. 하지만 hit -> hto 로 변화는 불가능합니다.
인덱스를 확인하지 않고 그냥 글자만 있는지 확인해서 틀렸습니다.
이것만 실수 안한다면 쉬운문제라고 생각합니다!