[프로그래머스/43163] 단어변환
in Study / Coding Test
☑️ 문제
☑️ 풀이
첫 번째 풀이 (DFS)
//시간: 0.18ms
//메모리: 87.1MB
import java.util.*;
class Solution {
public int answer = 100;
public boolean[] visited;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
boolean isPossible = false;
for (String str : words) {
if (str.equals(target)) {
isPossible = true;
break;
}
}
if (!isPossible) {
return 0;
}
dfs(begin, target, words, 0);
return answer;
}
public void dfs(String current, String target, String[] words, int depth) {
// target과 일치하면 최소 변환 횟수 저장
if (current.equals(target)) {
answer = Math.min(depth, answer);
return;
}
for (int i = 0; i < words.length; i++) {
if (!visited[i] && converted(current, words[i])) {
visited[i] = true;
dfs(words[i], target, words, depth + 1);
visited[i] = false;
}
}
}
public boolean converted(String current, String word) {
int cnt = 0;
for (int i = 0; i < current.length(); i++) {
if (current.charAt(i) != word.charAt(i)) {
cnt++;
}
if (cnt > 1) {
return false;
}
}
return cnt == 1;
}
}
- DFS에 적용한 개념 정리
- DFS는 “재귀(혹은 스택) 기반의 깊이 우선 탐색”을 수행하는 알고리즘
- 한 경로를 깊게 탐색하다가 더 이상 진행할 수 없으면 이전 단계로 돌아가 다른 경로를 탐색해야 한다.
- 모든 가능한 변환 경로를 고려
- 특정 단어에서 한 글자만 바꿔서 만들 수 있는 모든 후보를 탐색해야 한다.
- 단순한 배열 순차 탐색이 아니라, 현재 단어에서 한 글자 차이 나는 모든 단어를 찾아 DFS 탐색해야 한다.
- 백트래킹(Backtracking) 적용
- 한 경로로 탐색한 후, 다른 경로도 탐색할 수 있도록 방문 여부를 되돌려야 한다.
- 방문 여부를 체크하여 중복 탐색 방지
visited배열을 사용하여 방문한 단어는 다시 방문하지 않도록 관리한다.
- DFS는 “재귀(혹은 스택) 기반의 깊이 우선 탐색”을 수행하는 알고리즘
- 최단 변환 과정을 찾아야 하기 때문에 BFS 방식이 더 적절하다.
두 번째 풀이 (BFS)
//시간: 0.64ms
//메모리: 90.7MB
import java.util.*;
class Pair {
String str;
int depth;
public Pair (String str, int depth) {
this.str = str;
this.depth = depth;
}
}
class Solution {
public int answer = 0;
public boolean[] visited;
public int solution(String begin, String target, String[] words) {
visited = new boolean[words.length];
boolean isPossible = false;
for (String str : words) {
if (str.equals(target)) {
isPossible = true;
break;
}
}
if (!isPossible) {
return 0;
}
return bfs(begin, target, words);
}
public int bfs(String begin, String target, String[] words) {
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(begin, 0));
while (!queue.isEmpty()) {
Pair pair = queue.poll();
String current = pair.str;
int depth = pair.depth;
if (current.equals(target)) {
return depth;
}
for (int i = 0; i < words.length; i++) {
if (!visited[i] && converted(current, words[i])) {
visited[i] = true;
queue.add(new Pair(words[i], depth + 1));
}
}
}
return 0;
}
public boolean converted(String current, String word) {
int cnt = 0;
for (int i = 0; i < current.length(); i++) {
if (current.charAt(i) != word.charAt(i)) {
cnt++;
}
if (cnt > 1) {
return false;
}
}
return cnt == 1;
}
}
- BFS로 다시 풀어보았다.
- BFS에 적용한 개념 정리
- BFS는 큐(Queue) 기반의 너비 우선 탐색을 수행하는 알고리즘
- 한 단계씩 넓게 탐색하며, 모든 인접한 노드를 먼저 방문한 후 다음 깊이를 탐색한다.
- 최단 경로 문제에 가장 적합한 탐색
- 모든 가능한 변환 경로 고려
- 현재 단어에서 한 글자만 다른 단어를 찾아 탐색해야 한다.
- 변환 가능한 모든 단어를 큐에 삽입하여 레벨 단위로 탐색을 진행한다.
- DFS처럼 한 경로를 끝까지 탐색하는 것이 아니라, 가까운 변환부터 순차적으로 탐색한다.
- 최단 경로 보장
- BFS는 한 단계씩 진행되기 때문에, 가장 먼저
target에 도달하는 경로가 최단 거리임을 보장한다. depth를 증가시키며 탐색하고,target과 일치하면 즉시 탐색을 종료한다.
- BFS는 한 단계씩 진행되기 때문에, 가장 먼저
- 방문 여부를 체크하여 중복 탐색 방지
visited배열을 사용하여 이미 탐색한 단어는 다시 방문하지 않는다.
- BFS는 큐(Queue) 기반의 너비 우선 탐색을 수행하는 알고리즘
