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

문제

 

풀이

BFS가 DFS보다 어렵게 느껴져서 연습을 위해 풀어보았다. 처음에는 감을 아예 못 잡아서 헤맸는데, 백준의 숨바꼭질과 비슷하다는 생각이 들어서 비슷한 느낌으로 구현하게 되었다.

BFS DFS를 익혀가면서 느끼는 건데, visited를 int 배열로 구현할 것인지, boolean 배열로 구현할 것인지 항상 헷갈린다.

 

words 안에 target이 없는 경우 바로 answer를 0으로 리턴한다.

check 메서드는 한 글자만 다른지 확인하는 역할을 한다. cntIndex 메서드는 그냥 중복이 싫어서 따로 만든 메서드이다.

BFS 메서드에서는 단어 변경 가능한 경우, next(다음 단어 할당할 변수)에 words[i]를 넣는다.

next와 target이 같은 경우 words에서의 now 인덱스를 찾아 visited[now 인덱스]를 리턴한다. 처음에 리턴 값을 visited[next 인덱스] 로 설정해서 답이 틀렸었다.. visited[next 인덱스]를 리턴하면 당연히 아직 방문하지 않았으므로 0이 리턴된다.

next와 target이 다른 경우 queue에 next를 넣고 visited[next 인덱스] 값을 visited[now 인덱스]로 업데이트한다.

 

정답 코드

import java.util.*;

class Solution {
    
    static int[] visited;
    
    public int solution(String begin, String target, String[] words) {
        visited = new int[words.length];
        
        int answer = 0;
        int cnt = 0;
        for (int i = 0; i < words.length; i++) {
            if (target.equals(words[i])) {
                cnt++;
            }
        }
        if (cnt == 0) { // words 안에 target이 없는 경우
            return answer;
        }
        
        answer = BFS(begin, target, words);
        
        return answer;
    }
    
    static boolean check(String start, String word) { // 한 글자만 다른지 확인
        int cnt = 0;
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) != word.charAt(i)) { // 글자가 다를 때마다 cnt 증가
                cnt++;
            }
        }
        if (cnt == 1) {
            return true; // 한 글자만 다르면 true
        } else {
            return false;
        }
    }
    
    static int cntIndex(String word, String[] words) { // visited 인덱스 구하는 메서드
        for (int i = 0; i < words.length; i++) {
            if (word.equals(words[i])) {
                return i;
            }
        } return 0;
    }
    
    static int BFS(String begin, String target, String[] words) {
        Queue<String> q = new LinkedList<>();
        q.offer(begin); // 큐에 begin 넣기
        
        visited[cntIndex(begin, words)] = 1; // 시작점 visited 1로 설정
        
        while(!q.isEmpty()) {
            String now = q.poll();
            for (int i = 0; i < words.length; i++) {
                String next;
                if (check(now, words[i]) == true) {
                    next = words[i];
                    
                    if(next.equals(target)) { // next와 target과 같으면 답 리턴
                        return visited[cntIndex(now, words)];
                    }
                    q.offer(next);
                    visited[i] = visited[cntIndex(now, words)] + 1;
                }
            }
        } return 0;
    } 
}