99클럽 코테 스터디 33일차 TIL [DFS, BFS]

- 오늘의 학습 키워드 : DFS, BFS

[문제 이름 : 아이템 줍기 (프로그래머스, Lv 3)]

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

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        boolean isEmpty = true;
        for(String word : words) {
            if(word.equals(target)) {
                isEmpty = false;
                break;
            }
        }
        // 변환할 수 없는 경우
        if(isEmpty) return 0;
        return bfs(begin, target, words);
    }
    
    private int bfs(String begin, String target, String[] words) {
        Queue<Word> queue = new LinkedList<>();
        boolean[] visited = new boolean[words.length];
        
        queue.add(new Word(begin, 0));
        
        while(!queue.isEmpty()) {
            Word cur = queue.poll();
            String curWord = cur.word;
            int curDepth = cur.depth;
            
            if(curWord.equals(target)) {
                return curDepth;
            }
            
            for(int i=0; i<words.length; i++) {
                if(!visited[i] && canChange(curWord, words[i])) {
                    visited[i] = true;
                    queue.add(new Word(words[i], curDepth + 1));
                }
            }
        }
        return 0;
    }
    
    private boolean canChange(String w1, String w2) {
        int diff = 0;
        for(int i=0; i<w1.length(); i++) {
            if(w1.charAt(i) != w2.charAt(i)) {
                diff++;
            }
            
            if(diff > 1) break;
        }
        
        if(diff == 1) {
            return true;
        } else {
            return false;
        }
    }
    
    class Word {
        String word;
        int depth;
        
        Word(String word, int depth) {
            this.word = word;
            this.depth = depth;
        }
    } 
}

[풀이 과정]

1. 현재 단계와 해당 단계에 해당하는 String을 저장하는 Word 클래스를 만들어준다.

2. 만약 words배열에 target이랑 일치하는 단어가 없는 경우, 변환할 수 없으므로 0을 리턴한다.

3. bfs로 순환하며 일치하는 단어가 words내에 있는지 찾는다. 

4. 이때, 변환할 수 있는 단어인지를 보기 위해서 한글자만 다른 단어로 변경이 가능한 것들을 판별하기 위해 canChange 함수를 구현했다.

 

풀이 시간 : 20분