프로그래머스_단어변환_깊이/너비우선탐색(java)

단어 변환

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java

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

solution - 1) 그래프의 인접리스트 이용 (ArrayList 배열) / 큐 이용 (BFS)

1. 한 글자 차이나는 단어들 간에 간선을 연결한다.

2. 이 값을 저장하는 인접 리스트에 넣고 (9 ~27)

3. 배열에 타겟 스트링이 있는지 확인 후 없으면 0을 반환한다. (num변수 이용 / 25, 29 ~ 31)

4. 큐를 이용해 최단탐색 거리를 구한다. (33 ~ 52)

5. 타겟을 발견하면 while문에서 나간 후 탐색값을 출력한다.

import java.util.*;
 
class Solution {
    public int solution(String begin, String target, String[] words) {
        String temp = begin;
        int num = 0;
        ArrayList<Integer>[] list = new ArrayList[words.length+2];
        int count = 0;
        for(int j = 0; j < words.length+1; j++) {
            list[j] = new ArrayList<Integer>();
            
            for(int m = 0; m < words.length; m++) {
                count = 0;
                for(int i = 0; i < temp.length(); i++) {
                    if(temp.charAt(i) != words[m].charAt(i)) {
                        count++;
                    }
                }
                if(count == 1) {
                    list[j].add(m+1);
                }
            }
            
            if(j < words.length)    {temp = words[j]; 
            if(target.equals(words[j])) num =j+1;
            }
        }
        
        if(num == 0) {
            return 0;
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        int[] d = new int[words.length+2];
        Arrays.fill(d, -1);
        
        d[0] = 0;
        q.add(0);
        int u = 0;
        while(q.size() > 0) {
            u = q.poll();
            for(int e : list[u]) {
                if(d[e] == -1) {
                    d[e] = d[u]+1;
                    q.add(e);
                }
            }
            if(num == u) {
                break;
            }
            
        }
        return d[num];
    }
}

solution - 2) 참고하기

1. 노드 클래스를 만들어 이용

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