알맹이방
[프로그래머스] 단어 변환 - java 본문
class Solution {
static int sum_count = Integer.MAX_VALUE; //최솟값을 찾기 위한 count
void dfs(boolean[] visited, String target, String[] words, String begin, int count){
//target 이라면 count가 sum_count보다 작으면 갱신해줌
if(begin.equals(target)){
if(sum_count>count){
sum_count=count;
}
return ;
}
for(int i = 0; i<words.length; i++){
if(!visited[i]&&check(begin, words[i])){
visited[i]=true;//중요, 무한루프에 빠질 가능성 없애줌
dfs(visited, target, words, words[i], count+1);
visited[i]=false;
}
}
}
//한글자만 바뀌는지 체크하는 함수
public boolean check(String str1, String str2){
int num =0;
for(int i =0; i<str1.length(); i++){
if(str1.charAt(i)!=str2.charAt(i)){
num++;
}
}
if(num==1){
return true;
}
return false;
}
//메인함수
public int solution(String begin, String target, String[] words) {
dfs(new boolean[words.length],target, words, begin, 0);
if(sum_count == Integer.MAX_VALUE){
return 0;
}
return sum_count;
}
}
'알고리즘 > [2021] 프로그래머스' 카테고리의 다른 글
[프로그래머스] 모의고사 -JAVA (0) | 2021.06.01 |
---|---|
[프로그래머스] 여행경로 - java (0) | 2021.06.01 |
[프로그래머스] 가장 큰 수 - java (0) | 2021.05.31 |
[프로그래머스] 위장 - C++ (0) | 2021.05.31 |
[프로그래머스] 전화번호 목록 - C++ (0) | 2021.05.31 |
Comments