BFS
프로그래머스 레벨2의 단어 변환 문제이다.
이 문제는 가장 짧은 변환 과정을 찾아야하고 bfs 는 최단거리를 보장해주는 알고리즘이므로 bfs 를 사용해야한다.
좀 더 공부해봐야 알겠지만 dfs 는 최단 거리가 보장이 안될 수도 있지 않을까?
bfs 문제를 많이 풀어보지는 않아서 정확히는 모르겠지만 전에 푼 문제처럼 Queue 를 이용한다.
풀이
- 너비 우선 탐색 알고리즘을 이용하여 탐색한다.
- 큐에서 idx, move 의 초기값(0, 0)을 꺼내서 visited 에 방문 여부 겸 이동 수를 기록
- 탐색 조건에 의해 변환할 수 없는 경우의 수는 걸러지고 남은 경우들은 각자의 최선의 선택으로 탐색
- 탐색 후 다음 좌표를 큐에 저장하고 다음 좌표의 방문 여부 겸 이동 수를 visited 에 기록
- 각자의 최선의 선택으로 탐색한 경우만 남았으므로 최단 변환 과정은 bfs의 값을 인덱스로 하는 visited 의 값
- 큐가 비어서 탐색을 진행할 수 없는 경우 bfs 메서드는 0을 반환
- 탐색 종료 후 bfs 의 결과 값을 인덱스로 하는 visited 의 값을 반환(0 이면 변환 불가라는 뜻이므로 0)
최종 코드
import java.util.*;
class Solution {
// 너비 우선 탐색
public int bfs(String[] new_words, int[] visited, String target) {
Queue<int[]> que = new LinkedList<>();
// 초기값 (idx, move) = (0, 0)
que.add(new int[2]);
// que 에서 idx 와 move 를 꺼내서 사용하며
// que 가 비었다는건 words 를 모두 방문했다는 뜻이므로 변환 불가라는 뜻
while(!que.isEmpty()) {
int[] now = que.poll();
int idx = now[0];
int move = now[1];
// 탐색 조건
// 1. 방문하지 않은 words
// 2. 바뀐 글자가 1개
for (int i = 1; i < new_words.length; i++) {
int diff = 0;
// 바뀐 글자가 1개 뿐인지 체크
for (int j = 0; j < new_words[i].length(); j++) {
if (new_words[idx].charAt(j) != new_words[i].charAt(j)){
diff += 1;
}
}
if (visited[i] == 0 && diff == 1) {
// 조건에 맞을 경우 이동수 +1
// visitied[i] 에 이동수 기록
move += 1;
visited[i] = visited[idx] +1;
// target 으로 변환 시 해당 visited의 인덱스 i 반환
if (new_words[i].equals(target)) {
return i;
}
que.add(new int[]{i, move});
}
}
}
return 0;
}
public int solution(String begin, String target, String[] words) {
String[] new_words = new String[words.length +1];
new_words[0] = begin;
for (int i = 0; i < words.length; i++) {
new_words[i +1] = words[i];
}
int[] visited = new int[new_words.length];
int result = bfs(new_words, visited, target);
// result = 도착점의 visited 인덱스
// result 가 0 이면 변환 불가라는 의미
// result 가 0 이 아니면 visited[result] 가 이동수
return result == 0 ? 0 : visited[result] ;
}
}'알고리즘 > DFS 및 BFS' 카테고리의 다른 글
| [알고리즘] BFS 입문(JAVA) (0) | 2023.10.22 |
|---|---|
| [알고리즘] DFS 입문(JAVA) (0) | 2023.10.15 |