[프로그래머스] 단어 변환 / DFS/BFS(그래프탐색)

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

프로그래머스

---

---

코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        int[] visited = new int[words.length];
        Queue<Integer> q = new LinkedList<>();
        int cnt;
        
        for (int i = 0; i < words.length; i++) {
            
            cnt = 0;
            for (int j = 0; j < begin.length(); j++) { // 한글자 차이나는 것을 찾는거
                if(begin.charAt(j) == words[i].charAt(j)) cnt++;
            } // for j

            if(cnt == begin.length()-1) { // 단어 차이가 1개일 경우에만
                q.offer(i); // 큐에 추가
                visited[i] = 1; // 방문 처리
            } // if

        } // for i

        while (!q.isEmpty()) {
            int x = q.poll(); // 0(hot 인덱스)

            for (int i = 0; i < words.length; i++) {
                // 0이 아니면 방문을 했기때문에 다시 방문하지않겠다.
                if(visited[i] != 0) continue;

                cnt = 0;
                for (int j = 0; j < words[i].length(); j++) {
                    if(words[x].charAt(j) == words[i].charAt(j)) cnt++;
                }

                if (cnt == words[i].length()-1){
                    q.offer(i);
                    visited[i] = visited[x] + 1;
                }
            }

        } // while

        for (int i = 0; i < words.length; i++) {
            if (target.equals(words[i])) {
                answer = visited[i];
                break;
            }
        }

        return answer;
    }
}

---

begin인 문자열을 시작으로 글자가 1글자만 차이나는 것을 찾아야 한다.

즉, 노드 레벨이 0인거 부터 큐에 담는 작업을 한다.

큐에 다 담았으면 큐가 빌 때가지 반복을 한다.

while문 안에서 큐에 있는 원소를 하나 꺼낸 뒤 words 문자열 배열의 크기만큼 for문을 돌린다.

(문자열 배열을 다 탐색해야하기 때문에 문자열 배열의 크기만큼 for문을 돌리는 것)

문자열 배열안에서 방문을 했던 문자열이라면 다시 for문을 돌린다.

만약 방문하지 않은 문자열이라면 q에서 꺼낸 문자열과 i번째에 해당하는 문자열과 단어 차이가 1개인지 체크를 한 뒤 단어 차이가 1개라면 큐에 담은 뒤에 방문처리를 해준다.

 

큐가 다 빌때까지의 작업이 끝났다면

target과 동일한 문자가 있는지 찾은 후 answer 변수에 방문처리를 하면서 누적했던 값을 할당해준 뒤 break를 만나서 빠져나오게된다.

 

* 처음에 visited 배열을 boolean으로 했었는데 true, false로 방문처리만 하게되면 몇 번째에 target 단어를 찾는지 체크를 할 수 없어서 int[]로 수정하였다.