(Java)프로그래머스 코딩테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS) - 단어 변환

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43163#qna

코딩테스트 연습 - 단어 변환

2. 나의 풀이

class Solution {
    public int solution(String begin, String target, String[] words) {
        //words의 최대 길이로 answer 선언
        int answer = words.length + 1;
        //words배열을 순환하는 반복문
        for(int i = 0; i < words.length; i = i + 1) {
        	//words 배열의 각 인덱스를 방문했는지 확인할 boolean 	배열
        	boolean [] visited = new boolean[words.length];
        	if(compareString(begin, words[i])) {
        		answer = Math.min(answer, countConversion(words[i], target, i, 1, words, visited));
        	}
        }
        //answer가 그대로일 경우 변환이 불가능한 경우이므로 0을 리턴
        if(answer == words.length + 1) {
        	return 0;
        }
        
        return answer;
    }
    
    //word 배열의 각 인덱스 문자와 begin을 비교하여 1단어만 차이나는지 확인해줄 메소드
    public boolean compareString(String begin, String word) {
    	int cnt = 0;
    	for(int i = 0; i < begin.length(); i = i + 1) {
    		if(begin.charAt(i) != word.charAt(i)) {
    			cnt++;
    		}
    	}
    	return cnt == 1;
    }
    
    //begin에서 target까지 변환 횟수를 반환할 메소드
    public int countConversion(String begin, String target, int index, int cnt, String [] words, boolean [] visited) {
    	//함수에 들어온 begin과 target이 같은 경우 cnt를 리턴
    	if(begin.equals(target)) {
    		return cnt;
    	}
    	//들어온 begin의 인덱스를 방문했다는 것을 확인하기 위해 해당 인덱스의 visited을 true로 변경
    	visited[index] = true;
    	//현재 메소드에 들어온 begin과 다른 인덱스를 비교하여 1단어만 다른 단어를 찾으며 나아갈 반복문
    	int ans = 0;
    	for(int i = 0; i < words.length; i = i + 1) {
    		if(compareString(begin, words[i]) && !visited[i]) {
    			ans = countConversion(words[i], target, i, cnt + 1, words, visited);
    		}
    	}
    	return ans;
    }
}

3. 다른 사람 풀이

import java.util.LinkedList;
import java.util.Queue;

class Solution {

    static class Node {
        String next;
        int edge;

        public Node(String next, int edge) {
            this.next = next;
            this.edge = edge;
        }
    }

    public int solution(String begin, String target, String[] words) {
        int n = words.length, ans = 0;

        // for (int i=0; i<n; i++)
        //  if (words[i] != target && i == n-1) return 0;

        Queue<Node> q = new LinkedList<>();


        boolean[] visit = new boolean[n];
        q.add(new Node(begin, 0));

        while(!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.next.equals(target)) {
                ans = cur.edge;
                break;
            }

            for (int i=0; i<n; i++) {
                if (!visit[i] && isNext(cur.next, words[i])) {
                    visit[i] = true;
                    q.add(new Node(words[i], cur.edge + 1));
                }
            }
        }

        return ans;
    }

    static boolean isNext(String cur, String n) {
        int cnt = 0;
        for (int i=0; i<n.length(); i++) {
            if (cur.charAt(i) != n.charAt(i)) {
                if (++ cnt > 1) return false;
            }
        }

        return true;
    }    
}