[프로그래머스 : 레벨 3] 단어변환 : BFS(Java)

이번문제는 내가 DFS 알고리즘으로 문제를 풀려다가 중복되는 단어에서 어딜 먼저 접근해야하나라는 부분에서

막혀 답지를 봤다.

 

일단 문제부터 보자.

 

문제 설명

 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

입출력 예 설명

 

예제 #1

문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

 

이번문제를 답지를 보니 BFS로 문제를 풀었다.

 

나도 안그래도 '최소 몇단계의 과정' 이라는 말에 BFS로 푸는거 아닌가했지만 BFS문제의 아직 응용력이 떨어져서

문제에 적용시키지를 못했다.

 

소스를 보면 아래와 같다.

 

 

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();

		String[] words = { "lot", "dot", "dog", "hot", "log", "cog" };
		String begin = "hit";
		String target = "cog";

		System.out.println(p.solution(begin, target, words));
	}

    static class Node {
        String next; // 단어가 들어가는 부분
        int edge; // 해당 단어의 index인거 같음

        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; //배열 길이 
        int 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)) {  //값이  target과 같다면 들어가기
                ans = cur.edge; //해당 부분의 edge 즉 count를 값으로 주고 while break
                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;
    }

 

 

소스를 보면 BFS 부분은 일반적인 BFS와 다른점이 

            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)); //
                }
            }

위 부분인것 같다.

 

위부분은 큐에 있는 작업을 words에 있는 단어들과 일일히 비교해 알파벳이 하나 차이나는 단어를 방문 처리하고

그리고 queue에 넣고 Queue에 들어갈 node에 edge 부분은 queue에 넣을때마다 +1씩해주게 된다.

 

그리고 queue에 있는 작업의 단어가 target과 같다면 그제서야 answer의 값을 edge로 주고 queue를 도는 반복문을

빠져나오게 된다.

 

내가 하는말이 이해가 가질 않는다면 직접 손코딜 해보길 권한다.

 

느낀점

1. 최단경로를 찾는거라면 BFS 알고리즘으로 풀어봐라.