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

문제

프로그래머스-단어변환
begin의 단어를 target의 단어로 변환하는데 필요한 최소 단계를 구하는 문제.
변환 시 words내의 있는 단어를 이용하는데 한번에 한 글자(한개의 알파벳)만 바꿀 수 있고, 바꾼 단어도 words내에 있는 단어로만 변환할 수 있다.

풀이

문제를 이해하는데 조금 시간이 걸렸다.. 후..
words배열을 돌면서 첫번째부터 한글자 바꾸면서 돌았는데 예제1에서 3이 나왔다.
words에 있는 단어로만 변환하지 않았기 때문.. 그리고 words의 순서대로 돌 필요가 없었다.

words에 있는 단어인지 확인하기 위해 set을 사용했고, 변환한 단어들을 visit이라는 set을 만들어서
해당 단어를 변환하려는 시도가 있었는지 체크해서 중복으로 도는 것을 막았다.
target이 words - set에 없다면 변환할수 없기때문에 0을 바로 리턴한다.
words에 있는 단어와 현재 단계의 단어의 글자가 다른게 있고, 바꿨을 경우 words에 포함되어있으면서, 변환을 시도하지않았던 단어라면 step을 증가시킨후(변환 횟수), q에 넣고 진행하는 식으로 풀었다.

소스코드

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
	HashSet<String> set = new HashSet<>();
	HashSet<String> visit = new HashSet<>();
	int answer = Integer.MAX_VALUE;

	public int solution(String begin, String target, String[] words) {
		char[] b = begin.toCharArray();
		set.clear();
		for (int i = 0; i < words.length; i++) {
			set.add(words[i]);
		}
		
		if (!set.contains(target)) {
			return 0;
		}
		answer = Integer.MAX_VALUE;
		// 한글자만 바꿀수 있고 바꾸려는게 set안에 있으면
		Queue<Word> q = new LinkedList<>();
		q.add(new Word(b, 0));
		visit.add(begin);
		while (!q.isEmpty()) {
			Word curr = q.poll();
//			System.out.println(curr);
			if (target.equals(new String(curr.spelling))) {
				answer = Math.min(answer, curr.step);
			}
			for (int i = 0; i < words.length; i++) {
				for (int j = 0; j < words[i].length(); j++) {
					if (curr.spelling[j] != words[i].charAt(j)) {
						char tmp = curr.spelling[j];
						curr.spelling[j] = words[i].charAt(j);
						if (set.contains(new String(curr.spelling)) && !visit.contains(new String(curr.spelling))) {
							visit.add(new String(curr.spelling));
							q.add(new Word(curr.spelling.clone(), curr.step + 1));
						}
						curr.spelling[j] = tmp;
					}
				}
			}
		}
		return answer == Integer.MAX_VALUE ? 0 : answer;
	}

}

class Word {
	char[] spelling;
	int step;

	public Word(char[] spelling, int step) {
		super();
		this.spelling = spelling;
		this.step = step;
	}

	@Override
	public String toString() {
		return "Word [spelling=" + Arrays.toString(spelling) + ", step=" + step + "]";
	}

}

다른사람의 코드

어짜피 words내의 단어들로만 변환할 수 있으므로 words배열을 가지고 방문처리를 하는 코드이다.
한 글자만 다르면서 시도하지 않았던 단어의 경우 q에 추가하는 식으로 내코드랑 비슷한 원리긴 한데, 좀더 메모리 사용량부분에서 덜 소모하고 깔끔한 코드인 것 같다.

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