프로그래머스 Lv3_단어 변환_Java

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java

프로그래머스

 

import java.util.*;

class Solution {
    private String begin;
    private String target;
    private String[] words;
    private boolean[] visited;
    private int answer;
    
    public int solution(String begin, String target, String[] words) {
        this.begin = begin;
        this.target = target;
        this.words = words;
        this.visited = new boolean[words.length];
        this.answer = 0;
        
        if(!Arrays.asList(words).contains(target)) {
            return answer;
        }
        
        bfs();
        
        return answer;
    }
    
    public void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(begin, 0));
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            String str = node.str;
            int count = node.count;
            
            if(str.equals(target)) {
                answer = count;
                return;
            }
            
            for(int i = 0; i<words.length; i++) {
                if(!visited[i] && canChange(str, words[i])) {
                    visited[i] = true;
                    queue.add(new Node(words[i], count+1));
                }
            }
        }
    }
    
    public boolean canChange(String str, String str2) {
        int diffCount = 0;
        
        for(int i = 0; i<str.length(); i++) {
            if(str.charAt(i) != str2.charAt(i)) {
                diffCount++;
            }
            
            if(diffCount > 1) {
                return false;
            }
        }
        
        return diffCount == 1;
    }
    
    class Node {
        private String str;
        private int count;
        
        public Node(String str, int count) {
            this.str = str;
            this.count = count;
        }
    }
}

 

 

풀이

- 하나하나씩 다 bfs로 탐색

- 탐색하면서 변환할 수 있는 단어인지, 방문하지 않았는지 검사

- 검사후 bfs 돌면서 target에 도착하면 증가하던 count 가 정답

 

회고

- Swift 공부했을때 풀었던 문제였다

- java로 푸니까 생각보다 쉽지 않았다

- 그래도 bfs는 어느정도 풀 수 있을 것 같다