[Java] 프로그래머스 - 단어 변환 (3단계)

📝 문제

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

---

📝 답안

📌 작성 코드

import java.util.*;
class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean value = false;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(target)) {
                value = true;
                break;
            }
        }
        if (!value) return 0;
        
        ArrayList<char[]> list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            list.add(words[i].toCharArray());
        }
        
        char[] base = target.toCharArray();
        
        Queue<word> q = new LinkedList<>();
        q.add(new word(0, begin.toCharArray()));
        
        while (!q.isEmpty()) {
            word w = q.poll();
            char[] temp = w.list;
            int index = w.index;
            
            if (check(base, temp) == 0) return index;

            for (int i = 0; i < list.size(); i++) {
                char[] data = list.get(i);
                
                if (check(temp, data) == 1) q.add(new word(index+1, list.remove(i)));
            }
        }
        return 0;
    }
    
    public int check(char[] a, char[] b) {
        int count = a.length;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == b[i]) count--;
        }
        
        return count;
    }
}

class word {
    int index;
    char[] list;
    public word (int i, char[] list) {
        this.index = i;
        this.list = Arrays.copyOf(list, list.length);
    }
}

---

✔ 정확성 테스트

테스트 1 〉 통과 (0.50ms, 83.1MB)
테스트 2 〉 통과 (0.40ms, 81.9MB)
테스트 3 〉 통과 (0.53ms, 69.9MB)
테스트 4 〉 통과 (0.39ms, 74.8MB)
테스트 5 〉 통과 (0.02ms, 75MB)

---

📌 코드 풀이

boolean value = false;
for (int i = 0; i < words.length; i++) {
	if (words[i].equals(target)) {
		value = true;
		break;
	}
}
if (!value) return 0;

• words에 target이 있는지 없는지 확인
• value가 false로 변함이 없으면 target이 없다는 뜻으로 0 리턴

ArrayList<char[]> list = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
	list.add(words[i].toCharArray());
}

• words의 단어들을 비교하기 편하게 char배열로 변환 후 ArrayList에 넣기

char[] base = target.toCharArray();

• target도 한번씩 확인을 해야하기 때문에 미리 char배열로 만들어놓기

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

• 너비우선탐색인 BFS로 탐색하기 위해서 Queue 선언

q.add(new word(0, begin.toCharArray()));

• 큐에 begin을 char배열로 변환하여 word 객체로 만들어서 넣기
• index는 0으로 시작

while (!q.isEmpty()) {
	--중략--
}

• q가 비워질 때까지 반복

word w = q.poll();
char[] temp = w.list;
int index = w.index;

• 큐의 제일 상단 값 가져오기
• word의 list와 index를 가져와 따로 변수에 미리 담아놓기

if (check(base, temp) == 0) return index;

• check() 함수로 temp와 target이 같은지 안같은지 비교. 같으면 해당 index 리턴

for (int i = 0; i < list.size(); i++) {
	char[] data = list.get(i);
	if (check(temp, data) == 1) q.add(new word(index+1, list.remove(i)));
}

• check() 함수의 리턴값이 1인 경우는 temp와 data의 글자가 한 개만 다르다는 뜻이므로 list에서 지우면서 q에 넣기

---

📌 후기

BFS로 비교적 간단하게 풀었음