[프로그래머스 Programmers] 단어 변환 (BFS 풀이)

like0·2022년 3월 11일
0

코테준비(JAVA)

목록 보기
8/37

문제 설명

문제 링크

생각 정리

//처음 문자(begin)를 bfs의 파라미터로 보내면서 bfs함수 실행한다.
//bfs함수내에서 queue에 처음 문자를 추가한다.
//queue가 빌 때까지 반복한다.
	//queue에서 꺼낸 문자열과 배열내 문자열이 같으면 리턴해
	//words 배열을 순회하면서
    	//방문했으면 넘어가
        //그 외에는 
            //문자 하나씩(queue에서 꺼낸 문자의 글자 하나하나와) 배열내 문자열에 해당 문자가 있느지 확인
            //같을때마다 count하기
            //문자열 길이만큼 반복이 끝났을 때, count+1이 문자열 길이라면 (한 개의 알파벳만 다른거임)
            //방문표시하고, queue에 넣는다.
            //단계를 업데이트 시켜준다.

정리된 생각에 대한 논리

생각정리 부분 중, "단계를 업데이트 시켜준다"는 부분을 구현할 때 고민했다.

queue에서 꺼낸 단어의 idx새롭게 탐색중인 단어의 idx를 둘 다 알아야했다.

새롭게 탐색중인 단어의 idx는 words 배열을 순회할 때의 idx로 나타내면 되었지만, queue에서 꺼낸 단어의 idx는 어떻게 할지 고민을 하였다.

-> 그래서 class를 하나 만들어서 문자열과 idx를 함께 나타낼 수 있도록 하였다. (begin문자와 words배열 내의 문자를 모두 idx로 나타내기 위해
begin의 idx를 0,
words배열 내 문자들의 idx는 배열내 idx+1로 지정해두었다.)

//queue에 String형태의 문자만 추가하는 것이 아니고, 
	문자와 해당 문자의 idx를 함께 추가해준다.
//이유는 현재 단계를 나타낼 때 필요하기 때문이다.

완성된 코드

import java.util.*;

public class StringANDIdx {
    String str;
    int idx;
    
    StringANDIdx(String str, int idx) {
        this.str = str;
        this.idx = idx;
    }
}


class Solution {
    
    public static boolean[] visited;
    public static int[] dis ;
    public static int answer = 0;
    public int solution(String begin, String target, String[] words) {
    
        visited = new boolean[words.length];
        dis = new int[words.length+1];
        
        if(Arrays.asList(words).contains(target)){
            bfs(begin, target, words);
            return answer;   
        } else {
            return 0;
        }
        
    }
    
    static void bfs(String begin, String target, String[] words) {
        Queue<StringANDIdx> queue = new LinkedList<>();
        queue.add(new StringANDIdx(begin, 0)); //단어와 idx를 함께 나타낸다.
        
        while(!queue.isEmpty()) {
            StringANDIdx output = queue.poll();
            
            if(output.str.equals(target)) 
                return ;
            
             for(int i=0; i< words.length; i++) {
                int cnt = 0;
                String next = words[i];
                 
                if(visited[i]) continue;
                else {
                    for(int j=0; j<output.str.length(); j++) {
                        if(next.charAt(j) == output.str.charAt(j)){
                            cnt++;
                        } 
                    }
                    
                    if(cnt == output.str.length()-1) {
                        visited[i] = true;
                        queue.add(new StringANDIdx(words[i], i+1)); //단어와 idx를 함께 나타낸다.
                        dis[i+1] = dis[output.idx] + 1; //이것을 위해 StringANDIdx 의 형태로 단어와 idx를 함께 queue에 저장해두었다.
                        answer = dis[i+1];
                    }
                         
                }
            }
        }
    }
}

소감


이 문제는 정말 많이 풀어보려고 노력을 많이 한 문제이다.
그래서 모든 테스트케이스를 통과했을 때의 감격했다 !!!!! 진짜진짜

최소 경로, 최소 단계 와 같은 문제는 BFS문제로 푸는 것이 효율적이라고 한다.
(BFS는 너비우선탐색이기 때문에, 목적지에 도착했을 때 바로 최소 경로라고 할 수 있기 때문이다. 하지만, DFS는 목적지에 도착했을 때 최소 경로라고 장담할 수 없다. )

profile
배우고 성장하는 개발자가 되기!

0개의 댓글