[프로그래머스] 단어 변환(깊이우선탐색)

프로그래머스

DFS(깊이우선탐색)

 

프로그래머스

단어 변환

 

 

문제 정리

1. 두 개의 단어와 단어의 집합이 들어있는 배열이 주어진다.
2. 한 번에 한 개의 알파벳을 바꿀 수 있으며 words에 있는 단어로만 변환이 가능하다.
3. 최소 몇 단계의 과정을 거쳐 begin단어가 target 단어로 변환할 수 있는가
4. 각 단어는 소문자로 주어지며 변환할 수 없는 경우에는 0을 return 한다.

 

 

시작하기 전 접근 방법

1. 깊이우선탐색을 이용하여 하나씩 모든 과정을 탐색한다.
2. 탐색여부를 확인하기 위한 visited배열 생성
3. 단어에 대하여 한 글자 빼고 나머지가 모두 같은 단어를 찾는다.
4. 찾은 단어는 탐색 여부를 true로 설정한다.
5. true일 경우 cnt를 증가시키고 dfs 재귀함수를 다시 호출한다.
6. 목표 단어에 도달했을 때 다시 이전 상태로 돌아가야 하기 때문에 false로 바꾼다. 해당 단어를 처리한 후에 다시 방문 여부를 해제하고 다른 경로를 통해 같은 단어를 처리하기 위해서이다.

입출력 예

 

 

1. 깊이우선탐색을 이용하여 진행한다. 먼저 dfs메서드를 생성하며 최종 출력해야 하는 answer과 방문여부를 체크할 boolean 타입에 1차원 배열을 만든다.
2. dfs메서드에서 begin단어와 target단어가 같은 경우 cnt를 answer로 리턴한다.

class Solution {
        static boolean[] visited;
        static int answer = 0;
        
        ..........
        
public static void dfs(String begin, String target, String[] words, int cnt){
        //begin : 시작단어
        //target : 찾는 단어
        // word : 단어가 있는 배열
        // cnt : answer
        if(begin.equals(target)){
            answer = cnt;
            return;
        }

 

 

3. 반복문을 이용하여 방문여부를 체크하는 visited배열이 true라면 넘어가서 다음 단어를 확인한다.
4. 단어길이는 동일하기 때문에 각 단어를 한 글자씩 비교하며 해당 단어가 단어에 1 글자씩 바꿀 수 있기 때문에 단어길이 -1만큼 가다면 begin단어를 해당 단어로 바꾸고 cnt를 1 증가한다.

 

	if(visited[i]){
		continue;
	}
	int n = 0;
	for(int j=0; j<begin.length();j++){
		if(begin.charAt(j)==words[i].charAt(j)){
		n++;
		}
	}

 

 

5. 단어가 1글자 빼고 같을 때 방문 여부를 true로 변경하고 dfs 함수를 다시 호출한다.
6. 그리고 visited를 다시 false로 바꾸는 이유는 다음 재귀함수를 호출해서 원하는 타깃이 아니라면 이전으로 다시 돌아오기 위해서 false로 바꾸는 것이다.
6-1. 간단히 쉽게 말하면, visited [i]=false은 해당 단어 처리가 끝난 후에는 해당 단어를 다시 방문할 수 있도록 하기 위함이다.

if(n==begin.length()-1){
	visited[i]=true;
	dfs(words[i],target,words,cnt+1);
	visited[i]=false;
}

 

 

최종코드

class Solution {
        static boolean[] visited;
        static int answer = 0;
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        dfs(begin,target,words,0);
        return answer;
    }
    
    public static void dfs(String begin, String target, String[] words, int cnt){
        //begin : 시작단어
        //target : 찾는 단어
        // word : 단어가 있는 배열
        // cnt : answer
        if(begin.equals(target)){
            answer = cnt;
            return;
        }
        for(int i=0; i<words.length;i++){
            if(visited[i]){
                continue;
            }
            int n = 0;
            for(int j=0; j<begin.length();j++){
                if(begin.charAt(j)==words[i].charAt(j)){
                    n++;
                }
            }
            if(n==begin.length()-1){
                visited[i]=true;
                dfs(words[i],target,words,cnt+1);
                visited[i]=false;
            }
        }
        
    }
        
}