참고
문제해설
문제 로직고민
NOTE
•
변환에 대한 최소비용이므로 BFS를 사용하면 될것같다.
◦
단어 리스트를 방문할 수 있는 조건 ⇒ 단어 길이 n에서 n-1만큼 동일해야한다.
◦
한번 방문한 단어는 방문하지 않는다.
•
단어 길이 n에서 n-1만큼 동일한 것이 변환조건이다.
◦
가장 단순한 탐색방법은 단어 리스트를, 모두 순회하면서 하는건데 효율적인가?
◦
최악의 경우 단어길이 10, 단어의 개수 50일 때 변환하는 조건이 없다고 가정한다.
◦
결국 단어 50을 모두 방문했을때 없으면 실패하므로 그렇게 복잡하진 않을것 같다.
작성코드
NOTE
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
Queue<int[]> queue = new LinkedList();
boolean[] visited = new boolean[words.length];
queue.offer(new int[]{-1, 0});
while(!queue.isEmpty()){
int[] cur = queue.poll();
String curWord = cur[0] == -1 ? begin : words[cur[0]];
int time = cur[1];
if(curWord.equals(target)) return time;
for(int i=0; i<words.length; i++){
if(visited[i]) continue;
String word = words[i];
int temp = 0;
for(int j=0; j<curWord.length(); j++){
if(word.charAt(j) == curWord.charAt(j)) temp++;
}
if(temp == curWord.length() -1){
visited[i] = true;
queue.offer(new int[]{i, time+1});
}
}
}
return 0;
}
}
Java
복사
문자열 비교부분이 최적화 가능한지 궁금하다.
다른사람 풀이
NOTE
import java.util.LinkedList;
import java.util.Queue;
class Solution {
static class Node {
String next;
int edge;
public Node(String next, int edge) {
this.next = next;
this.edge = edge;
}
}
public int solution(String begin, String target, String[] words) {
int n = words.length, ans = 0;
// for (int i=0; i<n; i++)
// if (words[i] != target && i == n-1) return 0;
Queue<Node> q = new LinkedList<>();
boolean[] visit = new boolean[n];
q.add(new Node(begin, 0));
while(!q.isEmpty()) {
Node cur = q.poll();
if (cur.next.equals(target)) {
ans = cur.edge;
break;
}
for (int i=0; i<n; i++) {
if (!visit[i] && isNext(cur.next, words[i])) {
visit[i] = true;
q.add(new Node(words[i], cur.edge + 1));
}
}
}
return ans;
}
// 문자가 1개이상 차이나면 false반환
static boolean isNext(String cur, String n) {
int cnt = 0;
for (int i=0; i<n.length(); i++) {
if (cur.charAt(i) != n.charAt(i)) {
if (++ cnt > 1) return false;
}
}
return true;
}
}
Java
복사
문자열 비교를 더 효율적으로 진행