[프로그래머스] 단어 변환

문제 설명

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

문제 풀이

• BFS를 이용하여 풀이하였다.
• 각 단어의 인덱스를 번호로 두고 각 번호끼리 이동할 수 있는 Map을 만들어 준다. (한글자만 다른지 확인)
• begin에서 한글자만 다른 번호들을 큐에 넣고 BFS를 진행하다 target과 같아지면 변환 횟수 리턴

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int targetN = -1;
    public List<List<Integer>> map = new ArrayList<>();
    
    public class Point {
        int n, t;

        public Point(int n, int t) {
            this.n = n;
            this.t = t;
        }
    }

    boolean isDiffOneChar(String a, String b) {
        int diffCnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i) != b.charAt(i)) {
                if (++diffCnt > 1) return false;
            }
        }
        if (diffCnt == 1) return true;
        else return false;
    }

    public int solution(String begin, String target, String[] words) {
        //초기화
        for (int i = 0; i < words.length; i++) {
            if (target.equals(words[i])) {
                targetN = i;
                break;
            }
        }
        if (targetN == -1) return 0;
        for (int i = 0; i < words.length; i++) 
            map.add(new ArrayList<>());
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (isDiffOneChar(words[i], words[j])) {
                    map.get(i).add(j);
                    map.get(j).add(i);
                }
            }
        }
        
        //BFS 시작
        Queue<Point> q = new ArrayDeque<>();
        boolean[] chk = new boolean[words.length];
        for (int i = 0; i < words.length; i++) {
            if (isDiffOneChar(begin, words[i])) {
                chk[i] = true;
                q.add(new Point(i, 1));
            }
        }
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.n == targetN) return cur.t;
            for (int i = 0; i < map.get(cur.n).size(); i++) {
                int next = map.get(cur.n).get(i);
                if (chk[next]) continue;
                chk[next] = true;
                q.add(new Point(next, cur.t + 1));
            }
        }
        return 0;
    }
}