ALGORITHM/PROGRAMMERS
[프로그래머스] 단어 변환
0298
2021. 8. 11. 09:48
https://programmers.co.kr/learn/courses/30/lessons/43163
코딩테스트 연습 - 단어 변환
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수
programmers.co.kr
2021-08-11
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
if(!Arrays.asList(words).contains(target)) return 0;
int answer = 0;
Queue<String> q = new LinkedList<>();
boolean[] vtd = new boolean[words.length];
q.add(begin);
loop:while(!q.isEmpty()) {
int size = q.size();
while(size > 0) {
String tmp = q.poll();
if(tmp.equals(target)) break loop;
for(int i = 0; i < words.length; i++) {
int count = 0;
if(!vtd[i]) {
for(int k = 0; k < words[i].length(); k++) {
if(tmp.charAt(k) != words[i].charAt(k)) {
count++;
}
}
if(count == 1) {
q.add(words[i]);
vtd[i] = true;
}
}
}
size--;
}
answer++;
}
return answer;
}
}
|
cs |
#문제풀이
words 길이가 길지 않아서 bfs 돌려서 하나하나 체크했다.
