[Lv.3] 단어 변환 : Java

프로그래머스

 

 

 

이해하기

처음 접근 방식은 다음과 같았다.

1. BFS 문제인 것 같다!
2. 둘의 문자가 다르면 bfs를 호출하자.
3. 서로 한 글자만 다른 문자로 변경한다.
4. count!

첫 코드는 stack overflow가 떠서 bfs가 아닌걸까...? 하고 dfs로 다시 접근해봤다.

1. DFS로 풀어보자!
2. 둘의 문자가 같거나, words 안에 target이 없으면 바로 return 0
3. 서로 다르면 dfs 호출
4. 같아지면 끝나도록 if문 작성
5. 방문처리하며 counting
6. counting의 Min값 반환

class Solution {
    public int solution(String begin, String target, String[] words) {
        if (begin == target || !words.toString().contains(target)) {
            return 0;
        }

        boolean[] visited = new boolean[words.length];
        return dfs(begin, target, words, visited, 0);
    }

    public int dfs(String begin, String target, String[] words, boolean[] visited, int count) {
        if (begin == target) {
            return count;
        }

        String temp = "";

        for (int i = 0; i < words.length; i++) {
            int diff = 0;
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) != words[i].charAt(j)) {
                    diff++;
                }
            }

            if (!visited[i] && diff == 1) {
                temp += words[i];
                visited[i] = true;
                break;
            }
        }

        dfs(temp, target, words, visited, count + 1);

        return count;
    }
}

 

두 번째로 작성했던 코드는 위와 같다.

테스트 코드 5번만 성공하고 나머지 실패해서 20점짜리 풀이였다.

아마도 '둘의 문자가 같거나, words 안에 target이 없으면 바로 return 0' 부분에서 얻어 걸린 것 같다.

 

 

도저히 안 되겠어서 참고한 블로그는 아래!

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

 

이 분의 접근 방식은 아래와 같다.

1. 한 글자 빼고 나머지가 같은 단어를 words에서 찾는다.
2. 찾은 단어를 visited = true로 설정해준다.
3. cnt를 증가시키며 dfs 함수를 재귀 호출한다.
4. 모든 경우의 수를 보기 위해 visited = false로 재설정한다!!
5. begin과 target이 같은 경우, cnt를 answer에 대입하고 종료한다.

내가 생각했던 방법과 비슷하지만 내 로직에서는 4번이 빠진 것 같았다!

그럼 접근은 비슷하게 했지만 구현 문제라는 것...^^

다시 한 번 풀어보자.

 

 

문제풀이

class Solution {
    static boolean[] visited;
    static int answer;
    
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }

    public void dfs(String begin, String target, String[] words, int count) {
        if (begin.equals(target)) {
            answer = count;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }
            
            int diff = 0;
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) != words[i].charAt(j)) {
                    diff++;
                }
            }

            if (diff == 1) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }
        }
    }
}

 

    static boolean[] visited;
    static int answer;

 

visited와 answer은 파라미터로 넘겨주지 않아도 되도록 전역 변수로 설정!

항상 이 부분을 까먹는다 ㅋㅋ...

 

        visited = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;

 

words 길이에 맞게 visited 배열을 선언해주고 dfs 함수를 호출한다.

dfs 파라미터 중 0은 count 변수로 쓰인다.

 

        if (begin.equals(target)) {
            answer = count;
            return;
        }

 

begin과 target이 같으면 answer에 count 값을 넣어준다.

이 부분에서 어떻게 min 값을 찾는거지?? 싶었는데, 디버깅해보니 아래와 같은 흐름인 것 같다.

 

가장 긴 탐색 값 → 그보다 작은 값 → ... → 가장 작은 값!

 

이런 과정을 통해 결과적으로 가장 작은 값을 찾아가는 것 같다.

 

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }

 

이미 방문한 곳이라면 그냥 넘어가기

 

            int diff = 0;
            for (int j = 0; j < begin.length(); j++) {
                if (begin.charAt(j) != words[i].charAt(j)) {
                    diff++;
                }
            }

 

이 부분은 내 두 번째 풀이와 같아서 pass

 

            if (diff == 1) {
                visited[i] = true;
                dfs(words[i], target, words, count + 1);
                visited[i] = false;
            }

 

 

나는 이 부분에서 visited[i] = true 까지만 작성하였는데, 재탐색을 위해 false로 다시 변경해주는 부분이 추가되어야 했다!

하... 이런게 젤 어렵단 말이지 ㅜㅅㅜ

 

 

 

이해는 했으니 다시 풀어봐야지...