[Programmers] 단어 변환

[문제 링크]

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

프로그래머스

 

[풀이 과정]

bfs를 통해 갈 수 있는 곳을 하나씩 저장하여 방문하면서

가장 먼저 target과 같은 문자열이 나오면 각각 count한 숫자를 반환한다.

 

[코드]

import java.util.*;

// 편하게 String과 int를 넣기 위해 만든 class
class A {
    String str;
    int count;
    
    public A(String str, int count) {
        this.str = str;
        this.count = count;
    }
}

class Solution {
    boolean[] visited;
    String begin;
    String target;
    String[] words;
    int answer;
    
    public int solution(String begin, String target, String[] words) {
        answer = 0;
        visited = new boolean[words.length];
        this.begin = begin;
        this.target = target;
        this.words = words;
        
        bfs();
        
        // 초기값이 0이기 때문에 bfs에서 target을 찾지 못하면
        // 알아서 0으로 return 함
        return answer;
    }
    
    public void bfs() {
        Queue<A> queue = new LinkedList<>();
        queue.add(new A(begin, 0));
        
        while(!queue.isEmpty()) {
            A cur = queue.poll();
            String str = cur.str;
            int count = cur.count;
            
            // bfs로 반복중에 가장 빠르게 target과 같으면 answer에 저장해주고 break
            if(target.equals(str)) {
                answer = count;
                break;
            }
            
            for(int i = 0; i < words.length; i++) {
                if (strDiff(str, words[i]) == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(new A(words[i], count+1));
                }
            }
        }
        
        return;
    }
    
    public int strDiff (String a, String b) {
        int diff = 0;
        
        for(int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                diff++;
            }
        }
        
        return diff;
    }
}

[회고]

풀이 방법이 빨리 떠올라 생각보단 쉬웠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.