오늘은 프로그래머스의 단어 변환이라는 문제를 풀어 보았다.
문제 설명은 다음과 같다.
문제 설명
두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.
- 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
- words에 있는 단어로만 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.
제한사항
- 각 단어는 알파벳 소문자로만 이루어져 있습니다.
- 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
- words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
- begin과 target은 같지 않습니다.
- 변환할 수 없는 경우에는 0를 return 합니다.
위 문제를 보고 풀이를 생각해 보았다.
해당 문제는 dfs를 사용하여 단어가 한개 다른 문자로 계속 바꾸다가 target 단어와 같아지면 움직인 횟수를 반환하면 되겠다고 생각이 들었다.
문제 풀이는 다음과 같다.
class Solution {
int answer = Integer.MAX_VALUE;
String[] words;
public int solution(String begin, String target, String[] words) {
boolean[] visited = new boolean[words.length];
boolean flag = false;
this.words = words;
for (int i = 0; i < words.length; i++) {
flag = flag || words[i].equals(target);
}
if (!flag)
return 0;
for (int i = 0; i < words.length; i++) {
int count = 0;
for (int j = 0; j < words[i].length(); j++) {
if (begin.charAt(j) != words[i].charAt(j))
count++;
}
if (count == 1) {
visited[i] = true;
dfs(words[i], target, 1, visited);
visited[i] = false;
}
}
return answer == Integer.MAX_VALUE ? 0 : answer;
}
private void dfs(String currentString, String target, int count, boolean[] visited) {
if (currentString.equals(target)) {
answer = Math.min(answer, count);
}
for (int i = 0; i < words.length; i++) {
int failCount = 0;
for (int j = 0; j < words[i].length(); j++) {
if (currentString.charAt(j) != words[i].charAt(j))
failCount++;
}
if (!visited[i] && failCount == 1) {
visited[i] = true;
dfs(words[i], target, count + 1, visited);
visited[i] = false;
}
}
}
}우선 전역변수로 answer를 선언하고 정수의 최댓값을 지정해준다.
이유는 이동 횟수를 최솟값을 넣기 위해 비교를 하는데 처음에는 정수에서 나올 수 있는 최댓값을 설정해야 비교한값을 넣을 수 있다고 생각해서이다.
그리고 모든 함수에서 words값을 사용하기 위해 words를 전역변수로 선언해준다.
다음은 메인함수에서 불리안 배열 visited 변수를 선언해준다.
이유는 방문을 한 문자열인지 구분하기 위해서이다.
그리고 전역변수인 words에 매개변수로 받은 words를 삽입해준다.
다음으로 첫번째 반복문에 들어가는데 target이 문자열 배열에 존재하지 않으면 목표 문자로 만들 수 없기 때문에 반복문을 돌려서 target문자열이 있는지 확인하고 있으면 넘어가고 없으면 0을 반환한다.
다음 반복문은 문자열 배열의 길이만큼 반복을 돌고 각 문자마다 원래 문자와 같거나 2개 이상이 다를 경우 넘기고 1개만 다를 경우 방문처리 후 재귀함수 dfs로 들어가게 된다.
모든 작업이 끝난 후 answer가 정수의 최댓값이면 목적지에 도달할 수 없는 경우이기 때문에 0을 반환하고 아니면 answer를 그대로 반환한다.
다음은 재귀함수 내부의 로직이다.
우선 현재 문자열이 target과 같으면 answer에 원래 있던 값과 count를 비교하여 더 작은값을 넣어준다.
다음 반복문은 문자열 배열의 길이만큼 반복을 돌고 각 단어마다 현재 단어와 1개만 다르고 방문하지 않았으면 다시 재귀함수를 호출하여 반복하게 된다.
이렇게 풀이를 하니 정답을 받을 수 있었다.
