문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
각 단어는 알파벳 소문자로만 이루어져 있습니다.
각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
begin과 target은 같지 않습니다.
변환할 수 없는 경우에는 0를 return 합니다.
입출력 예
begin target words return
"hit" "cog" ["hot", "dot", "dog", "lot", "log", "cog"] 4
"hit" "cog" ["hot", "dot", "dog", "lot", "log"] 0
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.
진짜 어떡하지...
일단 생각한 게 저거 target이 words 안에 없으면 바로 0 return해버리기.... if문으로
글고 어.. 어...
bfs dfs겠지? 솔직히 카테고리 분류 안 됐으면 아이디어도 안 떠올랐을 듯...
그러면 일단 얘가 한 글자씩만 다르면은 서로 이어질 수 있다는 거니까 애들을 겁내 이어놓으면 되지 않을까???
bfs dfs 둘 다 될 것 같은데 일단 bfs로 갈겨보..자.....
외워두자 bfs는 큐 dfs는 스택!!!!!
하
못하겠다
타겟이
일단 다른 글자 1일 때만 true return하는 메소드 만들었다...
진짜 남노씨 코드 베끼고 어찌저찌
코드 완성...
class Solution {
public int solution(String begin, String target, String[] words) {0
if (!Arrays.asList(words).contains(target)) {
return 0;
}
boolean[] visited = new boolean[words.length];
Queue<WordStep> queue = new LinkedList<>();
queue.add(new WordStep(begin, 0));
while (!queue.isEmpty()) {
WordStep current = queue.poll();
if (current.word.equals(target)) {
return current.step;
}
for (int i = 0; i < words.length; i++) {
if (!visited[i] && canChange(current.word, words[i])) {
visited[i] = true;
queue.add(new WordStep(words[i], current.step + 1));
}
}
}
return 0;
}
boolean canChange(String word1, String word2) {
int count = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
count++;
}
}
if (count == 1) {
return true;
}
return false;
}
class WordStep {
String word;
int step;
WordStep(String word, int step) {
this.word = word;
this.step = step;
}
}
}
했는데 왜 안 돌아가...
import문 직접 넣어줘야하는구만
귀찮으니까 * 로 넣어줬다
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
if (!Arrays.asList(words).contains(target)) {
return 0;
}
boolean[] visited = new boolean[words.length];
Queue<WordStep> queue = new LinkedList<>();
queue.add(new WordStep(begin, 0));
while (!queue.isEmpty()) {
WordStep current = queue.poll();
if (current.word.equals(target)) {
return current.step;
}
for (int i = 0; i < words.length; i++) {
if (!visited[i] && canChange(current.word, words[i])) {
visited[i] = true;
queue.add(new WordStep(words[i], current.step + 1));
}
}
}
return 0;
}
boolean canChange(String word1, String word2) {
int count = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
count++;
}
}
if (count == 1) {
return true;
}
return false;
}
class WordStep {
String word;
int step;
WordStep(String word, int step) {
this.word = word;
this.step = step;
}
}
}
성공~!
주석을 넣어보자
5개 중에 3개가 나온다 했으니까 코드를 이해하는 수밖에(외우는 수밖에) 없지 않겠습니까
import java.util.*;
class Solution {
public int solution(String begin, String target, String[] words) {
if (!Arrays.asList(words).contains(target)) {
return 0;
} // Arrays로 변환... target 단어 없으면 바로 0 return
boolean[] visited = new boolean[words.length]; // 방문 여부 boolean 배열 words 길이만큼~
Queue<WordStep> queue = new LinkedList<>(); // bfs는 큐..
queue.add(new WordStep(begin, 0)); // 첫 단어랑 처음 시작이니까 0으로 WordStep 만들어서 큐에 넣어줌
// 큐 빌 때까지 while문 돌림
while (!queue.isEmpty()) {
WordStep current = queue.poll(); // 탐색할 단어 큐에서 꺼냄..
if (current.word.equals(target)) {
return current.step;
} // 꺼낸 단어가 target 단어면 스텝 반환
// words 배열 돌면서 바꾸기 가능 단어 찾기
for (int i = 0; i < words.length; i++) {
// 방문 내역 없고 점프 가능 단어면
if (!visited[i] && canChange(current.word, words[i])) {
visited[i] = true; // 방문 이력 찍기
queue.add(new WordStep(words[i], current.step + 1)); // 큐에 넣어주자 점프햇으니까 스텝도 1 더해주고
}
}
}
return 0;
}
boolean canChange(String word1, String word2) {
int count = 0;
for (int i = 0; i < word1.length(); i++) {
if (word1.charAt(i) != word2.charAt(i)) {
count++;
}
}
if (count == 1) {
return true;
}
return false;
} // 바꿀 수 있는지(철자가 1개만 다른지) true false 반환
class WordStep {
String word; // 현재 단어
int step; // 지금이 몇 단계인지
WordStep(String word, int step) {
this.word = word;
this.step = step;
}
} // 단어랑 점프 횟수 저장 클래스
}
다시 풀라면 또 못 풀지도..
클났다
낼도 또 풀어보는 수밖에~!!